题解 P5387 【[Cnoi2019]人形演舞】

· · 题解

怎么没有题解，水一个。

考虑怎么算 SG(x) 。我们断言 SG(2^k+n) = n+1 (n\in[0,2^k))。

假设上述结论对所有 i<x 都成立，我们证明该结论对 x=2^k+n 成立。

若 x=2^k ，SG(x)=1。如果 y 的第 k 位为 1，则只能 y=x，否则如果不为 1，则 y \bigoplus x > x。综上 x 的后继状态只有 0，故 SG(x)=1。

对于 x = 2^k + n, n \in [0,2^k)，SG(x) = n 。依然考虑最高位，如果为 0 则 x \bigoplus y \in [2^k, 2^k+n)，显然这些后继的 SG 值包含了 [1,n]。注意到 0 也是 x 的后继，因此 [0,n] 都出现过。

否则，设去掉最高位的 y 为 y' ，有 y' \leq n 且 x \bigoplus y = n \bigoplus y'。设 m=2^{\lfloor \log_2 n \rfloor}，显然有 SG(n \bigoplus y') \leq m \leq n。

综上，x 后继的 SG 值的 \operatorname{mex} 为 n+1，则 SG(x)=n+1。

至此我们可以在 O(m \log m) 的时间内算出 [1,m] 的 SG 值，就是要选出 |V| 个数使得它们的 SG 值的异或和不为 0。

设 A_i = \sum_{x=1}^m [SG(x)=i]，B=A^{|V|}（这里的乘法是异或卷积运算），则选取 |V| 个数使得异或和为 x 的方案数即为 B_x。

那么现在的问题就是怎么做异或卷积快速幂，每次 FWT 一遍复杂度不太对，我们可以先 FWT 一次，然后用 FWT 后的数组做乘法，最后 FWT 回来，就可以做到 O(m \log |V|) 了。

至此我们在 O(m \log m + m \log |V|) 的时间内解决了这个简单的问题。

#include <bits/stdc++.h>
#define maxn 1048576
#define ll long long
const int mod=998244353;
const int inv2=(mod+1)/2;
int A[maxn],b[maxn],n,lim;
ll k;

int SG(int x){
    int len=1,sum=0;
    while(sum<x){
        sum+=len;
        if(sum>=x)return x-(sum-len);
        len<<=1;
    }
}

void FWT(int *a,int lim,int flag){
    for(int i=1;i<lim;i<<=1)
    for(int j=0;j<lim;j+=(i<<1))
    for(int k=0;k<i;++k){
        int a1=a[j+k],a2=a[j+k+i];
        a[j+k]=(a1+a2)%mod;a[j+k+i]=(a1-a2+mod)%mod;
        if(flag==-1){
            a[j+k]=(ll)a[j+k]*inv2%mod;a[j+k+i]=(ll)a[j+k+i]*inv2%mod;
        }
    }
}

void mul(int *a,int *b,int lim){
    for(int i=0;i<lim;++i)a[i]=(ll)a[i]*b[i]%mod;
}

void qpow(int *a,ll k,int lim){
    b[0]=1;FWT(b,lim,1);
    while(k){
        if(k&1)mul(b,a,lim);
        mul(a,a,lim);
        k>>=1;
    }std::memcpy(a,b,sizeof(b));
}

int main(){
    int max=0;lim=1;
    scanf("%lld%d",&k,&n);
    for(int i=1;i<=n;++i){
        int d=SG(i);
        A[d]++;
        max=std::max(max,d);
    }while(lim<=max)lim<<=1;
    FWT(A,lim,1);
    qpow(A,k,lim);
    FWT(A,lim,-1);
    int sum=0;
    for(int i=1;i<lim;++i)sum=(sum+A[i])%mod;
    printf("%d",sum);
    return 0;
}