题目传送门
题目大意
给定$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
/**
* Codeforces
* Problem#979E
* Accepted
* Time: 31ms
* Memory: 36100k
*/
#include <bits/stdc++.h>
using namespace std;
typedef bool boolean; const int N = , M = 1e9 + ; int add(int a, int b) {
a += b;
if (a >= M)
return a - M;
return a;
} int n, p;
int ar[N];
int pow2[N];
int f[N][N][N][N];
int C[N][N];
int Co[N], Ce[N]; inline void init() {
scanf("%d%d", &n, &p);
for (int i = ; i <= n; i++)
scanf("%d", ar + i);
} inline void prepare() {
pow2[] = ;
for (int i = ; i <= n; i++)
pow2[i] = add(pow2[i - ], pow2[i - ]); C[][] = ;
for (int i = ; i <= n; i++) {
C[i][] = C[i][i] = ;
for (int j = ; j < n; j++)
C[i][j] = add(C[i - ][j], C[i - ][j - ]);
} for (int i = ; i <= n; i++) {
for (int j = ; j <= n; j++)
if (j & ) {
Co[i] = add(Co[i], C[i][j]);
} else {
Ce[i] = add(Ce[i], C[i][j]);
}
}
} inline void solve() {
f[][][][] = ;
for (int i = ; i <= n; i++)
// enmuerating last status
for (int ob = ; ob < i; ob++) // odd black
for (int eb = ; ob + eb < i; eb++) // even black
for (int ow = ; ob + eb + ow < i; ow++) { // odd white
int lans = f[i - ][ob][eb][ow];
if (!lans)
continue;
int ew = i - ob - eb - ow - ;
if (ar[i] != ) { // here painted in white
int gama = pow2[ow + ew + eb];
f[i][ob][eb][ow] = add(f[i][ob][eb][ow], lans * 1ll * gama % M * Co[ob] % M);
f[i][ob][eb][ow + ] = add(f[i][ob][eb][ow + ], lans * 1ll * gama % M * Ce[ob] % M);
} if (ar[i] != ) { // here painted in black
int gama = pow2[ew + ob + eb];
f[i][ob][eb + ][ow] = add(f[i][ob][eb + ][ow], lans * 1ll * gama % M * Co[ow] % M);
f[i][ob + ][eb][ow] = add(f[i][ob + ][eb][ow], lans * 1ll * gama % M * Ce[ow] % M);
}
} int res = ;
for (int ob = ; ob <= n; ob++)
for (int eb = ; eb + ob <= n; eb++)
for (int ow = ; ow + eb + ob <= n; ow++)
if (((ob + ow) & ) == p)
res = add(res, f[n][ob][eb][ow]);
printf("%d\n", res);
} int main() {
init();
prepare();
solve();
return ;
}
Slower Solution
/**
* Codeforces
* Problem#979E
* Accepted
* Time: 31ms
* Memory: 300k
*/
#include <bits/stdc++.h>
using namespace std;
typedef bool boolean; const int N = , M = 1e9 + ; int add(int a, int b) {
a += b;
if (a >= M)
return a - M;
return a;
} int n, p;
int ar[N];
int pow2[N];
int f[N][][][]; inline void init() {
scanf("%d%d", &n, &p);
for (int i = ; i <= n; i++)
scanf("%d", ar + i);
pow2[] = ;
for (int i = ; i <= n; i++)
pow2[i] = add(pow2[i - ], pow2[i - ]);
} inline void solve() {
f[][][][] = ;
for (int i = ; i <= n; i++)
// enmuerating last status
for (int hob = ; hob < ; hob++) // exists odd black or not
for (int how = ; how < ; how++) // exists odd white or not
for (int par = ; par < ; par++) {
int lans = f[i - ][hob][how][par];
if (!lans)
continue;
if (ar[i] != ) { // here painted in white
if (!hob)
f[i][][][par ^ ] = add(f[i][][][par ^ ], lans * 1ll * pow2[i - ] % M);
else {
f[i][][][par ^ ] = add(f[i][][][par ^ ], lans * 1ll * pow2[i - ] % M);
f[i][][how][par] = add(f[i][][how][par], lans * 1ll * pow2[i - ] % M);
}
} if (ar[i] != ) { // here painted in black
if (!how)
f[i][][][par ^ ] = add(f[i][][][par ^ ], lans * 1ll * pow2[i - ] % M);
else {
f[i][][][par ^ ] = add(f[i][][][par ^ ], lans * 1ll * pow2[i - ] % M);
f[i][hob][][par] = add(f[i][hob][][par], lans * 1ll * pow2[i - ] % M);
}
}
}
int res = ;
for (int x = ; x < ; x++)
for (int y = ; y < ; y++)
res = add(res, f[n][x][y][p]);
printf("%d\n", res);
} int main() {
init();
solve();
return ;
}