cf979E(DP套DP)

|

题目链接

https://codeforces.com/contest/979/problem/E

题意

给定一个 $n\,(n\le50)$ 个点的图，点有白有黑有待染色，只能从编号小的点向编号大的点连边，现对这个图染色连边，问有多少种方案，使得该图有偶/奇数条黑白相间的路径。

题解

先考虑子 $DP$ ，若给定图，那么黑白相间的路径数可以用一个简单 $DP$ 来解决

$dp[i]=\sum_{j=1}^{n-1} dp[j]​$ ( $j​$ 与 $i​$ 异色)

由于只要判定奇偶性，又可写为

$dp[i]=xor_{j=1}^{i-1} dp[j]$

那么只有 $dp$ 值为 $1$ 的点的个数的奇偶性即可确定 $dp[i]$

设第 $i$ 个点为黑点，如果确定了 $dp=1$ 的白点数 $a$ ，那么 $dp[i]=1/0$ 的方案数均为 $2^{a-1}2^{i-1-a}=2^{i-2}$

但是如果 $a=0$ ，$dp[i]$ 只能等于 $1$ ，需要特判

因此在做外层 $DP$ 的时候，需要确定有无 $dp=1$ 的黑/白点，那么设 $d[i][j][k][v]$ 为到第 $i$ 个点，答案为 $j$ 的方案数( $k$ 和 $v$ 分别代表有无 $dp=1$ 的黑/白点)

然后分类讨论转移就可以了。。复杂度 $O(n)$




代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/**
 *　　　　　　  　　┏┓　　 　┏┓
 * 　　　　　  　　┏┛┗━━━━━━━┛┗━━━┓
 * 　　　　　  　　┃　　　　　　　┃ 　
 * 　　　　　  　　┃　　　━　　 　┃
 * 　　　　　  　　┃　＞　　　＜　┃
 * 　　　　　  　　┃　　　　　　　┃
 * 　　　　　  　　┃...　⌒　... 　┃
 * 　　　　　　  　┃              ┃
 * 　　　　　　  　┗━┓          ┏━┛
 * 　　　　　　　　　┃          ┃　Code is far away from bug with the animal protecting　　　　　　　　　　
 * 　　　　　　　　　┃          ┃   神兽保佑,代码无bug
 * 　　　　　　　　　┃          ┃　　　　　　　　　　　
 * 　　　　　　　　　┃          ┃  　　　　　　
 * 　　　　　　　　　┃          ┃
 * 　　　　　　　　　┃          ┃　　　　　　　　　　　
 * 　　　　　　　　　┃          ┗━━━┓
 * 　　　　　　　　　┃              ┣┓
 * 　　　　　　　　　┃              ┏┛
 * 　　　　　　　　　┗┓┓┏━━━━━━━━┳┓┏┛
 * 　　　　　　　　　　┃┫┫       ┃┫┫
 * 　　　　　　　　　　┗┻┛       ┗┻┛
 */ 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<set>
#include<bitset>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define eps 1e-8
#define succ(x) (1<<x)
#define lowbit(x) (x&(-x))
#define sqr(x) ((x)*(x))
#define mid (x+y>>1)
#define NM 55
#define nm 32768
#define pi 3.1415926535897931
const int inf=1e9+7;
using namespace std;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f*x;
}


int n,_p,a[NM];
ll p[NM],d[NM][2][2][2],ans;

int main(){
    n=read();_p=read();
    inc(i,1,n)a[i]=read();
    p[0]=1;inc(i,1,n)p[i]=p[i-1]*2%inf;
    if(a[1])d[1][1][1][0]=1;
    if(a[1]<=0)d[1][1][0][1]=1;
    inc(i,2,n)inc(j,0,1)inc(k,0,1)inc(v,0,1)if(d[i-1][j][k][v]){
	if(a[i]){
	    if(v){
		(d[i][j][k][v]+=d[i-1][j][k][v]*p[i-2]%inf)%=inf;
		(d[i][j^1][1][v]+=d[i-1][j][k][v]*p[i-2]%inf)%=inf;
	    }else{
		(d[i][j^1][1][v]+=d[i-1][j][k][v]*p[i-1]%inf)%=inf;
	    }
	}
	if(a[i]<=0){
	    if(k){
		(d[i][j][k][v]+=d[i-1][j][k][v]*p[i-2]%inf)%=inf;
		(d[i][j^1][k][1]+=d[i-1][j][k][v]*p[i-2]%inf)%=inf;
	    }else{
		(d[i][j^1][k][1]+=d[i-1][j][k][v]*p[i-1]%inf)%=inf;
	    }
	}
    }
    inc(j,0,1)inc(k,0,1)ans+=d[n][_p][j][k];
    ans%=inf;
    return 0*printf("%lld\n",ans);
}