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;

}

巴特西

vijos2055 移动金币

思路

代码

最新文章

热门文章