分析
一次移动后会让左边的空位减少若干,右边的空位增加若干,从而可以转化为一个阶梯博弈。
不妨把左右反过来,那么就是要算有多少种方案满足编号为偶数的空位的异或和不为 $0$。
再转化问题,相当于求 $n-m$ 个物品放进 $m+1$ 个盒子中,使得编号为偶数的盒子中的物品数的异或和不为 $0$ 的方案数。
这个不为 $0$ 不好处理,可以容斥一下,变成算为 $0$ 的。那么就是每一位上为 $1$ 的数都要是偶数个。
考虑 DP。设 $dp_{i,j}$ 表示最高的 $i$ 位、还剩 $j$ 个物品没放的方案数,转移枚举放入的盒子数 $k$:
$$
{(m+1)/2\choose k}dp_{i,j}\to dp_{i-1,j-k\times 2^{i-1}}
$$
最后枚举没放的物品数,用把这些物品放到奇数盒子中去即可算出答案。
代码
// ====================================
// author: M_sea
// website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;
int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=150050+10;
const int mod=1e9+9;
int qpow(int a,int b) { int c=1;
for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
return c;
}
int n,m;
int fac[N],ifac[N];
int dp[19][N];
void init(int n) {
fac[0]=1;
for (int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
ifac[n]=qpow(fac[n],mod-2);
for (int i=n;i;--i) ifac[i-1]=1ll*ifac[i]*i%mod;
}
int C(int n,int m) {
if (n<m) return 0;
else return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main() {
n=read(),m=read(); init(n+m);
int l=1; while ((1<<l)<=n) ++l;
dp[l][n-m]=1;
for (int i=l;i;--i)
for (int j=0;j<=n-m;++j) {
if (!dp[i][j]) continue;
for (int k=0;k<=(m+1)/2&&k*(1<<(i-1))<=j;k+=2)
dp[i-1][j-k*(1<<(i-1))]=(dp[i-1][j-k*(1<<(i-1))]+1ll*dp[i][j]*C((m+1)/2,k))%mod;
}
int ans=0;
for (int i=0;i<=n-m;++i) ans=(ans+1ll*dp[0][i]*C(m/2+i,m/2))%mod;
printf("%d\n",(C(n,m)-ans+mod)%mod);
return 0;
}