题解 CF979E 【Kuro and Topological Parity】

da32s1da · 2019-01-20 15:40:06 · 题解

考虑一个O(n)的做法。

套路一下，把点分为偶黑,偶白,奇黑,奇白四类。（比如说，奇白代表有奇数条路径以该点为结尾且该点为白色）

考虑加入一个白色点\ i\ ，我们讨论一下

• 连到偶黑，路径条数加上一个偶数，奇偶性不变。
• 连到偶白和奇白，不是黑白相间的路径，路径条数奇偶性不变。
• 下面讨论一下奇黑的情况
  • 存在奇黑，我们可以挑出一个奇黑点来控制奇偶性，即这个白点作为奇白和偶白的方案数各为2^{i-2}
  • 不存在奇黑，它自己算一条黑白相间的路径，只能作为奇白

至此，加入白色点的讨论就结束了。

黑色自行分析

理解了讨论，代码也很好懂了

//f[i][_][ob][ow]表示第i个点，路径条数奇偶性为_，有无奇黑，有无奇白的方案数。
#include<cstdio>
const int mod=1e9+7;
const int N=60;
int n,p,_2[N],a[N];
int f[N][2][2][2],ans;
void add(int &x,int y){
    x+=y;
    if(x>=mod)x-=mod;
}
int main(){
    scanf("%d%d",&n,&p);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    _2[0]=1;
    for(int i=1;i<=n;i++)_2[i]=(_2[i-1]<<1)%mod;
    f[0][0][0][0]=1;
    for(int i=1;i<=n;i++)
    for(int _=0;_<=1;_++)
    for(int ob=0;ob<=1;ob++)
    for(int ow=0;ow<=1;ow++){
        int qwq=f[i-1][_][ob][ow];
        if(a[i]!=0){//白点
            if(ob){//讨论有无奇黑
                add(f[i][_][ob][ow],1ll*qwq*_2[i-2]%mod);
                add(f[i][_^1][ob][ow|1],1ll*qwq*_2[i-2]%mod);
            }else add(f[i][_^1][ob][ow|1],1ll*qwq*_2[i-1]%mod);
        }
        if(a[i]!=1){
            if(ow){
                add(f[i][_][ob][ow],1ll*qwq*_2[i-2]%mod);
                add(f[i][_^1][ob|1][ow],1ll*qwq*_2[i-2]%mod);
            }else add(f[i][_^1][ob|1][ow],1ll*qwq*_2[i-1]%mod);
        }
    }
    for(int ob=0;ob<=1;ob++)
    for(int ow=0;ow<=1;ow++)
    add(ans,f[n][p][ob][ow]);
    printf("%d\n",ans);
}