[数学记录]P5387 [Cnoi2019]人形演舞

· · 个人记录

题意 : 对一堆大小为 w 的石子，可以做以下操作 ：

选定 y\leq x ，使得 x{\ \rm xor\ }y<x ，并将石子数拿至 x{\ \rm xor\ }y。

现在有 n 堆石子，每一堆的大小都在 [1,m] 中。

两人轮流操作，不能操作者负。问先手必胜的情况数。

答案对 998244353 取模。

------------ 首先推一下 $\rm SG$ 函数。 首先显然有 $SG(0)=0$。 注意到 $y\leq x$ 的限制，考虑 $x$ 的最高位，设 $x=2^k+z\ (z<2^k)

若 y\leq 2^k ，则 y 可任取。后继状态有 2^k+[0,z)。

若 y> 2^k ，相当于求 z 的所有后继，只需考虑 SG(z)。

考虑归纳证明 ： 对于 x=2^k+z\ (z<2^k)，SG(x)=1+z。

对于 x=2^k 的情况，后继状态只有 0 ，则 SG(2^k)=1。

对于 x=2^k+z 的情况，后继状态有 \{2^k+[0,z)\} 以及 z 的后继。

则后继 SG 有 [0,z]∩[0,SG(z)) ，由归纳结论显然有 SG(z)\leq z。

所以 SG(2^k+z)=1+z。

容易求出 [1,m] 的 SG 值。

现在问题变成了 ： 在集合 S 中选择 n 次元素，使得异或和非 0 的方案数。

使用异或卷积快速幂即可。

复杂度 O(m\log m)。

#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 1050000
using namespace std;
const int mod=998244353;
ll powM(ll a,int t=mod-2){
  ll ret=1;
  while(t){
    if (t&1)ret=ret*a%mod;
    a=a*a%mod;t>>=1;
  }return ret;
}
void FWT(ll *F,int n)
{
  for (int len=1;len<n;len<<=1)
    for (int p=0;p<n;p+=len+len)
      for (int k=0;k<len;k++){
        ll sav0=F[p|k];
        F[p|k]=sav0+F[p|len|k];
        F[p|len|k]=sav0-F[p|len|k];
      }
  for (int i=0;i<n;i++)F[i]%=mod;
}
int n,m,h[MaxN];
ll k,F[MaxN];
int main()
{
  scanf("%lld%d",&k,&m);
  k%=(mod-1);
  for (n=1;n<=m;n<<=1);
  for (int i=1;i<=m;i++){
    h[i]=max(h[i>>1]<<1,i&1);
    F[(i^h[i])+1]++;
  }
  FWT(F,n);
  for (int i=0;i<n;i++)
    F[i]=powM(F[i],k);
  FWT(F,n);
  ll ans=(powM(m,k)-powM(n)*F[0])%mod;
  printf("%lld",(ans+mod)%mod);
  return 0;
}