Luogu

LOJ

分析

一次移动后会让左边的空位减少若干,右边的空位增加若干,从而可以转化为一个阶梯博弈。

不妨把左右反过来,那么就是要算有多少种方案满足编号为偶数的空位的异或和不为 $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;
}
最后修改:2021 年 01 月 07 日 09 : 27 PM