vijos2055 移动金币

题目链接

思路

首先这是一个阶梯博弈。

我们将金币两两组合，如果对方移动前一个，那么我们把后一个移动相同的距离，局面相当于没有变化。如果对方移动后一个，就相当于\(NIM\)游戏中，取走了一些石子。

所以这个游戏也就是金币两两组合后，有\(\lceil \frac{m}{2}\rceil\) 堆石子，进行\(NIM\)游戏

统计方案

然后考虑如何统计方案。

根据上面的结论。也就是我们要找出\(\lceil \frac{m}{2}\rceil\)堆石子，使他们个数异或和为0。

\(f[i][j]\)表示异或和的前i位异或起来为\(0\)，已经有了j个石子的方案数。

就有如下的转移\[f[i][j]=\sum\limits_{k=0}^{2 ^{2k}\le j\&k\le \lceil\frac{m}{2}\rceil}{f[i-1][j-2^{2k}]\times (^{\lceil \frac{m}{2} \rceil}_{2k})}\]

然后再考虑这\(\lceil \frac{m}{2} \rceil\)堆石子的位置。

利用隔板法。就相当于把\(\frac{m}{2}\)个挡板插到了长度为\(n-i\)(i为所放的石子长度)的序列里。

代码

/*
* @Author: wxyww
* @Date:   2019-05-11 18:24:32
* @Last Modified time: 2019-05-15 09:49:57
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 150000 + 100,mod = 1e9 + 9;
#define int ll
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int inv[N],f[20][N],jc[N];
int qm(int x,int y) {
    int ret = 1;
    for(;y;y >>= 1,x = 1ll * x * x % mod) 
        if(y & 1) ret = 1ll * ret * x % mod;
    return ret;
}
int C(int x,int y) {
    return 1ll * jc[x] * inv[y] % mod * inv[x - y] % mod;
}
signed main() {
    int n = read(),m = read();
    //预处理
    jc[0] = 1;
    for(int i = 1;i <= n + m;++i) jc[i] = 1ll * jc[i - 1] * i % mod;
    inv[0] = 1;
    for(int i = 1;i <= n + m;++i) inv[i] = qm(jc[i],mod - 2);

    int ans = C(n,m);
    n -= m;
    int num = (m + 1) >> 1;
    //dp
    f[0][0] = 1;
    for(int i = 1;i <= 19;++i) {
        int z = i - 1;
        for(int j = 0;j <= n;++j) {
            for(int k = 0;(k << z) <= j && k <= num;k += 2) {
                f[i][j] += 1ll * f[i - 1][j - (k << z)] * C(num,k) % mod;
                f[i][j] %= mod;
            }
        }
    }
    //统计答案
    for(int i = 0;i <= n;++i) {
        ans -= 1ll * f[19][i] * C(m / 2 + n - i,m / 2) % mod;
        ans = (ans + mod) % mod;
    }
    cout<<ans;
    return 0;
}