网站开发遵循的原则,涿州网站建设公司,编程培训机构需要什么资质,一般的电脑培训班要多少钱正题
题目链接:https://www.luogu.com.cn/problem/P5363 题目大意 1n1\times n1n的网格上有mmm个硬币#xff0c;两个人轮流向前移动一个硬币但是不能超过前一个硬币#xff0c;无法移动者输。 求有多少种情况先手必胜。 解题思路
竟然有我会的题#xff0c;我感动
位置做…正题
题目链接:https://www.luogu.com.cn/problem/P5363 题目大意
1×n1\times n1×n的网格上有mmm个硬币两个人轮流向前移动一个硬币但是不能超过前一个硬币无法移动者输。 求有多少种情况先手必胜。 解题思路
竟然有我会的题我感动
位置做差分再减去111之后就是一个经典的阶梯博弈问题了结论就是奇数位置的异或和。
但是这题是计数先让nnn减去mmm然后正难则反考虑求总方案和后手必胜的情况这样问题就变为有多少个长度为mmm的非负整数序列满足它们的和不超过nnn且奇数位置的异或和为000。
考虑枚举奇数位置的和奇数位置个数为z⌊m12⌋z\lfloor\frac{m1}{2}\rfloorz⌊2m1⌋设fif_ifi表示zzz个数的和为iii时异或和为000的方案数这个状态直接计算起来很难搞。
可以枚举每一个位的111的数量显然每一个位的111数量肯是偶数。然后用组合数转移即可。
然后设gig_igi表示m−zm-zm−z个数和不超过iii的方案数那么有gi∑j0i(jm−z−1m−z−1)g_i\sum_{j0}^i\binom{jm-z-1}{m-z-1}gi∑j0i(m−z−1jm−z−1)前缀和转移就好了。
然后答案就是(nmm)−∑i0nfign−i\binom{nm}{m}-\sum_{i0}^nf_ig_{n-i}(mnm)−∑i0nfign−i注意这里的nnn已经减去mmm了因为模数不是质数直接杨辉三角求就好了。
时间复杂度O(nmlogm)O(nm\log m)O(nmlogm)当然肯定是跑不满的 code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N2e5,P1e99;
ll n,m,ans,c[N][51],f[N],g[N];
signed main()
{scanf(%lld%lld,n,m);ans0;if(nm)return puts(0)0;c[0][0]1;for(ll i1;in;i)for(ll j0;jmin(i,m);j)c[i][j]((j?c[i-1][j-1]:0)c[i-1][j])%P;n-m;ll z(m1)/2;f[0]1;for(ll i1;i18;i)for(ll jn;j0;j--)for(ll k1;kz/2;k){if(j(k*(1i)))break;(f[j]f[j-k*(1i)]*c[z][2*k]%P)%P;}for(ll i0;in;i)g[i](g[i-1]c[im-z-1][m-z-1])%P;for(ll i0;in;i)(ansf[i]*g[n-i]%P)%P;printf(%lld\n,(c[nm][m]-ansP)%P);return 0;
}
