题目传送门 传送点 题目大意 给定$n$个标号依次为$1, 2, \cdots, n$的点，其中一些点被染成一些颜色，剩下的点没有染色。你需要添加一些有向边并将剩下的点染色，满足有向边从编号小
题目传送门
传送点
题目大意
给定$n$个标号依次为$1, 2, \cdots, n$的点，其中一些点被染成一些颜色，剩下的点没有染色。你需要添加一些有向边并将剩下的点染色，满足有向边从编号小的一端指向编号大的一端，图中所有黑白相错的路径的条数与$p$对2取模同余。
$1\leqslant n\leqslant 10^6$
想一下如何求DAG中黑白相错的路径的条数。用$g_{i}$表示$i$结尾的路径的条数。
考虑怎么转移，枚举前一个点，然后$g_{i} += g_{pre}[col_{pre}\neq col_{i}]$。
这里我们希望知道所有点的$g$的和的奇偶性。我们考虑每次加入一个点，我们希望知道它的$g$的奇偶性就能更新了。
它更新的时候的奇偶性只与$g_pre$的奇偶性以及$g$的颜色有关，因此我们可以将点分为四类：
- 奇黑点，$g_{p} \equiv 1 \pmod{2} \wedge col_{i} = black$
- 偶黑点，$g_{p} \equiv 0 \pmod{2} \wedge col_{i} = black$
- 奇白点，$g_{p} \equiv 1 \pmod{2} \wedge col_{i} = white$
- 偶白点，$g_{p} \equiv 0 \pmod{2} \wedge col_{i} = white$
然后假设当前的即将加入的点是白点，那么考虑它的连边
- 之前的白点对它的奇偶性没有影响，所以这之间的边可以任意连。
- 偶黑点对它的奇偶性也没有影响，所以这之间的边可以任意连。
- 考虑奇黑点
- 如果不存在奇黑点，那么当前点一定是奇白点（它自己的方案）。
- 如果存在奇黑点，每与一个奇黑点连边就会改变一次奇偶性，那么我们先拿走一个，剩下的任意连，拿走的这一个可以控制这个点方案数的奇偶性（比如考虑这个点之前当前点是奇白点，我希望它是奇白点，那么不连边）。因此恰好一半的任意连边方法使当前点的奇偶性为奇或偶。
对黑点可以作类似的讨论，然后我们可以愉快地得出结论：
- 如果当前不存在方案数为奇数的颜色与当前点相反的点，那么之前方案数乘上$2^{i - 1}$转移到当前点方案数为奇数的状态。
- 否则，对于当前点方案数为奇为偶各加上之前方案数乘$2^{i - 2}$。
状态用$f_{i, have\_odd\_white, have\_odd\_black, parity}$来表示。
时间复杂度$O(n)$。
Code
1 /** 2 * Codeforces 3 * Problem#979E 4 * Accepted 5 * Time: 31ms 6 * Memory: 36100k 7 */ 8 #include <bits/stdc++.h> 9 using namespace std; 10 typedef bool boolean; 11 12 const int N = 55, M = 1e9 + 7; 13 14 int add(int a, int b) { 15 a += b; 16 if (a >= M) 17 return a - M; 18 return a; 19 } 20 21 int n, p; 22 int ar[N]; 23 int pow2[N]; 24 int f[N][N][N][N]; 25 int C[N][N]; 26 int Co[N], Ce[N]; 27 28 inline void init() { 29 scanf("%d%d", &n, &p); 30 for (int i = 1; i <= n; i++) 31 scanf("%d", ar + i); 32 } 33 34 inline void prepare() { 35 pow2[0] = 1; 36 for (int i = 1; i <= n; i++) 37 pow2[i] = add(pow2[i - 1], pow2[i - 1]); 38 39 C[0][0] = 1; 40 for (int i = 1; i <= n; i++) { 41 C[i][0] = C[i][i] = 1; 42 for (int j = 1; j < n; j++) 43 C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]); 44 } 45 46 for (int i = 0; i <= n; i++) { 47 for (int j = 0; j <= n; j++) 48 if (j & 1) { 49 Co[i] = add(Co[i], C[i][j]); 50 } else { 51 Ce[i] = add(Ce[i], C[i][j]); 52 } 53 } 54 } 55 56 inline void solve() { 57 f[0][0][0][0] = 1; 58 for (int i = 1; i <= n; i++) 59 // enmuerating last status 60 for (int ob = 0; ob < i; ob++) // odd black 61 for (int eb = 0; ob + eb < i; eb++) // even black 62 for (int ow = 0; ob + eb + ow < i; ow++) { // odd white 63 int lans = f[i - 1][ob][eb][ow]; 64 if (!lans) 65 continue; 66 int ew = i - ob - eb - ow - 1; 67 if (ar[i] != 0) { // here painted in white 68 int gama = pow2[ow + ew + eb]; 69 f[i][ob][eb][ow] = add(f[i][ob][eb][ow], lans * 1ll * gama % M * Co[ob] % M); 70 f[i][ob][eb][ow + 1] = add(f[i][ob][eb][ow + 1], lans * 1ll * gama % M * Ce[ob] % M); 71 } 72 73 if (ar[i] != 1) { // here painted in black 74 int gama = pow2[ew + ob + eb]; 75 f[i][ob][eb + 1][ow] = add(f[i][ob][eb + 1][ow], lans * 1ll * gama % M * Co[ow] % M); 76 f[i][ob + 1][eb][ow] = add(f[i][ob + 1][eb][ow], lans * 1ll * gama % M * Ce[ow] % M); 77 } 78 } 79 80 int res = 0; 81 for (int ob = 0; ob <= n; ob++) 82 for (int eb = 0; eb + ob <= n; eb++) 83 for (int ow = 0; ow + eb + ob <= n; ow++) 84 if (((ob + ow) & 1) == p) 85 res = add(res, f[n][ob][eb][ow]); 86 printf("%d\n", res); 87 } 88 89 int main() { 90 init(); 91 prepare(); 92 solve(); 93 return 0; 94 }Slower Solution
1 /** 2 * Codeforces 3 * Problem#979E 4 * Accepted 5 * Time: 31ms 6 * Memory: 300k 7 */ 8 #include <bits/stdc++.h> 9 using namespace std; 10 typedef bool boolean; 11 12 const int N = 55, M = 1e9 + 7; 13 14 int add(int a, int b) { 15 a += b; 16 if (a >= M) 17 return a - M; 18 return a; 19 } 20 21 int n, p; 22 int ar[N]; 23 int pow2[N]; 24 int f[N][2][2][2]; 25 26 inline void init() { 27 scanf("%d%d", &n, &p); 28 for (int i = 1; i <= n; i++) 29 scanf("%d", ar + i); 30 pow2[0] = 1; 31 for (int i = 1; i <= n; i++) 32 pow2[i] = add(pow2[i - 1], pow2[i - 1]); 33 } 34 35 inline void solve() { 36 f[0][0][0][0] = 1; 37 for (int i = 1; i <= n; i++) 38 // enmuerating last status 39 for (int hob = 0; hob < 2; hob++) // exists odd black or not 40 for (int how = 0; how < 2; how++) // exists odd white or not 41 for (int par = 0; par < 2; par++) { 42 int lans = f[i - 1][hob][how][par]; 43 if (!lans) 44 continue; 45 if (ar[i] != 0) { // here painted in white 46 if (!hob) 47 f[i][0][1][par ^ 1] = add(f[i][0][1][par ^ 1], lans * 1ll * pow2[i - 1] % M); 48 else { 49 f[i][1][1][par ^ 1] = add(f[i][1][1][par ^ 1], lans * 1ll * pow2[i - 2] % M); 50 f[i][1][how][par] = add(f[i][1][how][par], lans * 1ll * pow2[i - 2] % M); 51 } 52 } 53 54 if (ar[i] != 1) { // here painted in black 55 if (!how) 56 f[i][1][0][par ^ 1] = add(f[i][1][0][par ^ 1], lans * 1ll * pow2[i - 1] % M); 57 else { 58 f[i][1][1][par ^ 1] = add(f[i][1][1][par ^ 1], lans * 1ll * pow2[i - 2] % M); 59 f[i][hob][1][par] = add(f[i][hob][1][par], lans * 1ll * pow2[i - 2] % M); 60 } 61 } 62 } 63 int res = 0; 64 for (int x = 0; x < 2; x++) 65 for (int y = 0; y < 2; y++) 66 res = add(res, f[n][x][y][p]); 67 printf("%d\n", res); 68 } 69 70 int main() { 71 init(); 72 solve(); 73 return 0; 74 }