题解：P10363 [PA2024] Monety

· · 题解

首先要判断什么样的状态是公平的。

可以发现，公平的状态最后一定是全部硬币都移除了，否则交换先后手是先手胜。

那么考虑能否给每个硬币一个权值，使得两人硬币权值和相等（也就是相差为 0）是状态公平的充要条件。

先给出赋权方法，对于一堆硬币，底部连续一段属于同一个人的硬币权值为 1，其余硬币权值是它下面硬币权值的 \frac 1 2。

例如 CCNNC 的权值为 [1,1,\frac 1 2,\frac 1 4,\frac 1 8]。

下面来说明为什么相差为 0 的状态是公平的。

设当前硬币最小的权值为 w。

首先可以发现这样的硬币至少有 2 枚，否则相差不为 0。

然后认为操作者移除自己的硬币减少相应的权值，移除对手的硬币增加相应的权值，最后权值小的就输了。

那么可以发现，这次移除硬币后，操作者权值至少减小 w。

因为根据等比数列求和，每个权值为 x 的硬币上方对手的权值和不超过 x-w。

其次，能够做到只减少 w 的权值，如果存在自己的硬币就直接移除，否则找到对面的权值为 w 的硬币，将其下方第一个自己的硬币移除，可以发现这样权值也减少 w。

因此，先后手各减少 w 的权值，权值相差依旧为 0。

接下来考虑怎么计数。

为了避免分数计算，将所有权值 \times 2^{m-1}。

特判掉 m=1 的情况。

考虑数位 DP，因为每一堆石子底部连续段长度不同，考虑在枚举到该堆石子最低位时加入，并钦定底部是 CC\cdots CN 还是 NN\cdots NC，同时记录权值 \ge 2^{m-2} 的权值差。

设 f_{i,j,k,l} 表示考虑了 2^i 以下的位，加入了 j 堆石子，\ge 2^{m-2} 的权值差为 k\times 2^{m-2}，其余位的权值差为 l\times 2^i。

转移时枚举新加入的底部为 CC\cdots CN 和 NN\cdots NC 的堆的数量，再枚举这一位有多少 C。

注意到这 3 个量联系并不大，可以分开 3 次转移，每次 O(n)。

最后 2^{m-2} 和全部相同的堆的转移也是类似的。

状态数为 O(m\times n\times nm\times n)，转移是 O(n) 的。

所以时间复杂度 O(n^4m^2)，使用滚动数组后空间大小为 O(n^3m)，实测最大耗时在 1s 以内。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int P=1e9+7,V1=1536,V2=32,M1=V1*2+1,M2=V2*2+1;
int n,m,k,sum,C[35][35],f[33][M1][M2],g[33][M1][M2],h[33][M1][M2],t[33][M1],ans[35];
char s[25];
inline int md(int x){
    return x>=P?x-P:x;
}
inline void Add(int &x,int y){
    if((x+=y)>=P)x-=P;
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=k;++i){
        scanf("%s",s);
        int t=m-1,fg=0;
        for(int j=0;j<m;++j){
            if(j&&s[j]!=s[j-1])fg=1;
            t-=fg;
            if(s[j]=='C')sum+=1<<t;
            else sum-=1<<t;
        }
    }
    n-=k,sum=abs(sum);
    for(int i=0;i<=n;++i)C[i][0]=1;
    for(int i=1;i<=n;++i)for(int j=1;j<=i;++j)C[i][j]=md(C[i-1][j]+C[i-1][j-1]);
    if(m==1){
        for(int i=0;i<=n;++i){
            if((i+sum&1)||sum>i)printf("0 ");
            else printf("%d ",C[i][i+sum>>1]);
        }
        return 0;
    }
    f[0][V1][V2]=1;
    for(int i=0;i<=m-2;++i){
        for(int j=0;j<=n;++j)for(int k=-V1;k<=V1;++k)for(int l=-V2;l<=V2;++l){
            int w=f[j][k+V1][l+V2];
            if(!w)continue;
            f[j][k+V1][l+V2]=0;
            int v=2*(i+1)-1;
            for(int t=0;t+j<=n;++t)
                Add(g[j+t][k+V1+t*v][l+V2],1ll*w*C[j+t][t]%P);
        }
        for(int j=0;j<=n;++j)for(int k=-V1;k<=V1;++k)for(int l=-V2;l<=V2;++l){
            int w=g[j][k+V1][l+V2];
            if(!w)continue;
            g[j][k+V1][l+V2]=0;
            int v=2*(i+1)-1;
            for(int t=0;t+j<=n;++t)
                Add(h[j+t][k+V1-t*v][l+V2],1ll*w*C[j+t][t]%P);
        }
        if(i==m-2)break;
        int o=sum>>i&1;
        for(int j=0;j<=n;++j)for(int k=-V1;k<=V1;++k)for(int l=-V2;l<=V2;++l){
            int w=h[j][k+V1][l+V2];
            if(!w)continue;
            h[j][k+V1][l+V2]=0;
            if((l+j&1)!=o)continue;
            for(int t=0;t<=j;++t)
                Add(f[j][k+V1][(l+(j-2*t)-o>>1)+V2],1ll*w*C[j][t]%P);
        }
    }
    int o=sum>>m-2&1;
    for(int j=0;j<=n;++j)for(int k=-V1;k<=V1;++k)for(int l=-V2;l<=V2;++l){
        int w=h[j][k+V1][l+V2];
        if(!w)continue;
        h[j][k+V1][l+V2]=0;
        if(l+k-o&1)continue;
        Add(t[j][(l+k-o>>1)+V1],w);
    }
    sum>>=m-1;
    for(int j=0;j<=n;++j)for(int k=-V1;k<=V1;++k){
        int w=t[j][k+V1];
        if(!w)continue;
        int v=k-sum;
        if(v%m!=0)continue;
        v/=m;
        for(int l=0;j+l<=n;++l)if(v<=l&&v+l>=0&&!(v+l&1))Add(ans[j+l],1ll*w*C[j+l][l]%P*C[l][v+l>>1]%P);
    }
    for(int i=0;i<=n;++i)printf("%d ",ans[i]);
    return 0;
}