LCI.CF979E Kuro and Topological Parity
我们考虑在一张染色完成的图里,我们连上了一条边,会有何影响?
- 在同色节点间连边——明显不会有任何影响
- 在异色节点间连边,但是出发点是个偶点(即有偶数条路径以其为终点的节点)——终点的路径数增加了,但增加的是偶数,故也无影响。
- 在异色节点间连边,但是出发点是个奇点——终点的路径数的奇偶态变化,有影响。
故我们只需要考虑状况三即可。
于是我们就可以构造出如下的DP:
设\(f[i,j,k,l]\)表示当前DP到了位置\(i\),总路径数是\(j\)(\(0/1\)),且无/有奇黑点,无/有奇白点。
下面以位置\(i+1\)填入白色为例:
- 存在至少一个奇黑点(即\(k=1\)),则对于任意一组其它\(i-1\)个节点的连边方式,总有一种方式使得总数为奇,一种方式使得总数为偶(受此奇黑点的控制)。于是就有 \(f[i,j,k,l]\times 2^{i-1}\rightarrow f[i+1,j,k,l]\)与\(f[i,j,k,l]\times 2^{i-1}\rightarrow f[i+1,\lnot j,k,\operatorname{true}]\)。
- 不存在奇黑点(即\(k=0\)),则无论怎么连,\(i+1\)的奇偶性都不会变化,始终为奇态(被看作是以它自己为起点的路径的终点)。故有\(f[i,j,k,l]\times 2^i\rightarrow f[i+1,\lnot j,k,\operatorname{true}]\)。
填入黑色则同理。
代码
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,p,a[100],f[100][2][2][2],bin[100],res;
//f[i][j][k][l]:the number of situations where there're odd/even roads which ends in i, there has(not) an odd black, has(not) an odd white
int main(){
scanf("%d%d",&n,&p),bin[0]=1;
for(int i=1;i<=n;i++)scanf("%d",&a[i]),bin[i]=(bin[i-1]<<1)%mod;
f[0][0][0][0]=1;
for(int i=0;i<n;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++)for(int l=0;l<2;l++){
if(!f[i][j][k][l])continue;
int tmp=f[i][j][k][l];
if(a[i+1]!=0){//can be white
if(k)(f[i+1][j][k][l]+=1ll*tmp*bin[i-1]%mod)%=mod,(f[i+1][j^1][k][true]+=1ll*tmp*bin[i-1]%mod)%=mod;
else (f[i+1][j^1][k][true]+=1ll*tmp*bin[i]%mod)%=mod;
}
if(a[i+1]!=1){//can be black
if(l)(f[i+1][j][k][l]+=1ll*tmp*bin[i-1]%mod)%=mod,(f[i+1][j^1][true][l]+=1ll*tmp*bin[i-1]%mod)%=mod;
else (f[i+1][j^1][true][l]+=1ll*tmp*bin[i]%mod)%=mod;
}
}
for(int k=0;k<2;k++)for(int l=0;l<2;l++)(res+=f[n][p][k][l])%=mod;
printf("%d\n",res);
return 0;
}