vijos2055 mobile gold coin

Title Link

thinking

First, it's a ladder game.

If the other side moves the former one, then we move the latter one the same distance, and the situation is equivalent to no change. If the opponent moves the latter one, it's equivalent to \ (NIM \) taking some stones in the game.

So this game is the combination of two gold coins. There are \ (\ lceil \frac{m}{2}\rceil \) stones to play \ (NIM \) game

Statistical scheme

Then consider how to count the options.

According to the above conclusion. That is to say, we need to find out \ (\ lceil \frac{m}{2}\rceil \) heaps of stones, so that the sum of their numbers is 0.

\(f[i][j] \) indicates that the first i-digit XOR of XOR and is \ (0 \), and there are already schemes of j stones.

There are the following transfers \ [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}})} \]

Then consider the location of this \ (\ lceil \frac{m}{2} \rceil \) heap.

Use the diaphragm method. It is equivalent to inserting \ (\ frac{m}{2} \) baffles into a sequence of \ (n-i\)(i is the length of the placed stones).

Code

/*
* @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();
    //Preprocessing
    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;
            }
        }
    }
    //Statistical answers
    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;
}

Tags: C++

Posted on Sun, 10 Nov 2019 08:41:11 -0800 by nova912