Luogu P5363 [SDOI2019]移动金币

话说这题放在智推里好久了的说，再不写掉对不起自己233

首先你要知道一个叫做阶梯Nim的东西，具体的可以看这篇博客

那么我们发现这和这道题的关系就很明显了，我们把两个金币之间的距离看作阶梯Nim的每一堆的石子个数

考虑阶梯Nim的结论：奇数编号堆的石子异或和为\(0\)，发现我们可以搞一个很暴力的DP出来

\(f_{i,j,k}\)表示当前放了前\(i\)堆石子，总共用了石子个数是\(j\)，其中奇数堆石子的异或和为\(k\)的方案数，转移的时候直接枚举当前堆拿了几个即可，复杂度\(O(n^3\times m)\)，显然无法通过此题

我们再来冷静一下，发现限制的条件是异或，那么果断想到从二进制的角度出发

先容斥一下，令\(f_{i,j}\)表示做了前\(i\)位的，奇数堆和为\(j\)且异或和为\(0\)的方案数，最后用隔板法综合偶数堆的情况然后用\(C_n^m\)减去即可

然后DP就很好转移了，我们从高到低枚举二进制位，然后枚举奇数堆的和，剩下枚举这一位是\(1\)的奇数堆的个数（显然必须为偶数），然后转移的时候乘上组合数即可

复杂度\(O(nm\times \log n)\)，足以通过本题的数据范围。当然提一下这题还有利用进位角度考虑然后再用MTT优化的\(O(m\log m\log n)\)的优秀做法因此是可以出一个加强版的233

#include<cstdio>

#define RI register int

#define CI const int&

using namespace std;

const int N=200005,R=20,mod=1e9+9;

int n,m,f[R][N],odd,even,num,ret,fact[N],inv[N];

inline void inc(int& x,CI y)

{

	if ((x+=y)>=mod) x-=mod;

}

inline int sub(CI x,CI y)

{

	int t=x-y; return t<0?t+mod:t;

}

inline int quick_pow(int x,int p=mod-2,int mul=1)

{

	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;

}

inline void init(CI n)

{

	RI i; for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;

	for (inv[n]=quick_pow(fact[n]),i=n-1;~i;--i) inv[i]=1LL*inv[i+1]*(i+1)%mod;

}

inline int C(CI n,CI m)

{

	return 1LL*fact[n]*inv[m]%mod*inv[n-m]%mod;

}

int main()

{

	RI i,j,k; scanf("%d%d",&n,&m); init(n+m);

	for (odd=m+1>>1,even=m+1-odd,num=n-m,f[R-1][num]=1,i=R-2;~i;--i)

	for (j=0;j<=num;++j) for (k=0;j+(1<<i)*k<=num&&k<=odd;k+=2)

	inc(f[i][j],1LL*f[i+1][j+(1<<i)*k]*C(odd,k)%mod);

	for (i=0;i<=num;++i) inc(ret,1LL*f[0][i]*C(i+even-1,even-1)%mod);

	return printf("%d",sub(C(n,m),ret)),0;

}

巴特西

Luogu P5363 [SDOI2019]移动金币

最新文章

热门文章