题解 CF979E 【Kuro and Topological Parity】

考虑一个$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); } ```