# vijos2055 mobile gold coin

## thinking

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
*/
#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 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() {
//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;
}
}
}
}