rockdu
Kuro has recently won the "Most intelligent cat ever" contest. The three friends then decided to go to Katie's home to celebrate Kuro's winning. After a big meal, they took a small break then started playing games.
Kuro challenged Katie to create a game with only a white paper, a pencil, a pair of scissors and a lot of arrows (you can assume that the number of arrows is infinite). Immediately, Katie came up with the game called Topological Parity.
The paper is divided into nn pieces enumerated from 11 to nn. Shiro has painted some pieces with some color. Specifically, the ii-th piece has color cici where ci=0ci=0 defines black color, ci=1ci=1 defines white color and ci=−1ci=−1 means that the piece hasn't been colored yet.
The rules of the game is simple. Players must put some arrows between some pairs of different pieces in such a way that for each arrow, the number in the piece it starts from is less than the number of the piece it ends at. Also, two different pieces can only be connected by at most one arrow. After that the players must choose the color (00 or 11) for each of the unpainted pieces. The score of a valid way of putting the arrows and coloring pieces is defined as the number of paths of pieces of alternating colors. For example, [1→0→1→0][1→0→1→0], [0→1→0→1][0→1→0→1], [1][1], [0][0] are valid paths and will be counted. You can only travel from piece xx to piece yy if and only if there is an arrow from xx to yy.
But Kuro is not fun yet. He loves parity. Let's call his favorite parity pp where p=0p=0 stands for "even" and p=1p=1 stands for "odd". He wants to put the arrows and choose colors in such a way that the score has the parity of pp.
It seems like there will be so many ways which satisfy Kuro. He wants to count the number of them but this could be a very large number. Let's help him with his problem, but print it modulo 109+7109+7.
The first line contains two integers nn and pp (1≤n≤501≤n≤50, 0≤p≤10≤p≤1) — the number of pieces and Kuro's wanted parity.
The second line contains nn integers c1,c2,...,cnc1,c2,...,cn (−1≤ci≤1−1≤ci≤1) — the colors of the pieces.
Print a single integer — the number of ways to put the arrows and choose colors so the number of valid paths of alternating colors has the parity of pp.
3 1-1 0 1
6
2 1 1 0
1
1 1-1
2
In the first example, there are 66 ways to color the pieces and add the arrows, as are shown in the figure below. The scores are 3,3,53,3,5 for the first row and 5,3,35,3,3 for the second row, both from left to right.
简单的小清新dp，考虑每次加一个点，枚举其它点向它的连边。如果加一个白点，那么会对答案有影响的只有原本黑色的点，黑点同理。那么状态显然，dp[i][j][k][l]表示有i个点，一共有j个黑点，有奇数条合法路径以它结尾的黑点有k个，有奇数条合法路径以它结尾的白点有l个，然后转移因为一个点也是路径，我们每次枚举奇偶性相反的状态转移就可以了，然后从n个点中选m个点的操作是一个组合数，预处理一下就好，复杂度O(n^5)。
code#1:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define LL long long
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int maxn = 55;
const int mod = 1e9 + 7;
int dp[maxn][maxn][maxn][maxn], now, ans;
int n, p, c[maxn], wht_tot, blk_even, wht_even, rw;
LL C[maxn][maxn], pow2[maxn];
void pre(int n) {
C[0][0] = 1;
For(i, 1, n) For(j, 0, i)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
pow2[0] = 1;
For(i, 1, n) pow2[i] = pow2[i - 1] * 2 % mod;
}
void Add(int & a, int b) {
a += b;
if(a > mod) a -= mod;
}
int main() {
scanf("%d%d", &n, &p), pre(n);
For(i, 1, n) scanf("%d", &c[i]);
if(c[1] == 1 || c[1] == -1) dp[1][1][1][0] += 1;
if(c[1] == 0 || c[1] == -1) dp[1][0][0][1] += 1;
For(i, 1, n - 1) {
For(blk_tot, 0, i) {
wht_tot = i - blk_tot;
For(blk_odd, 0, blk_tot) {
blk_even = blk_tot - blk_odd;
For(wht_odd, 0, wht_tot) {
wht_even = wht_tot - wht_odd;
now = dp[i][blk_tot][blk_odd][wht_odd];
if(c[i + 1] == 1 || c[i + 1] == -1) {
rw = 0;
For(to_wht_odd, 0, wht_odd) {
if(!rw) Add(dp[i + 1][blk_tot + 1][blk_odd + 1][wht_odd], (now * C[wht_odd][to_wht_odd] % mod) * pow2[blk_tot + wht_even] % mod);
else Add(dp[i + 1][blk_tot + 1][blk_odd][wht_odd], (now * C[wht_odd][to_wht_odd] % mod) * pow2[blk_tot + wht_even] % mod);
rw ^= 1;
}
}
if(c[i + 1] == 0 || c[i + 1] == -1) {
rw = 0;
For(to_blk_odd, 0, blk_odd) {
if(!rw) Add(dp[i + 1][blk_tot][blk_odd][wht_odd + 1], (now * C[blk_odd][to_blk_odd] % mod) * pow2[blk_even + wht_tot] % mod);
else Add(dp[i + 1][blk_tot][blk_odd][wht_odd], (now * C[blk_odd][to_blk_odd] % mod) * pow2[blk_even + wht_tot] % mod);
rw ^= 1;
}
}
}
}
}
}
For(i, 0, n) For(j, 0, n) For(k, 0, n) {
if(((j + k) & 1) == p) {
Add(ans, dp[n][i][j][k]);
//printf("%d %d %d %d : %d\n", n, i, j, k, dp[n][i][j][k]);
}
}
printf("%d", ans);
return 0;
}
但是实际上我们发现从n个点中选奇数个和从n个点中选偶数个是一样的方案数，总的方案数是2^n，那么每一种就是2^(n-1)，O(n^4)。
code#2:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define LL long long
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int maxn = 55;
const int mod = 1e9 + 7;
int dp[maxn][maxn][maxn][maxn], now, ans;
int n, p, c[maxn], wht_tot, blk_even, wht_even, rw;
LL C[maxn][maxn], pow2[maxn];
void pre(int n) {
C[0][0] = 1;
For(i, 1, n) For(j, 0, i)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
pow2[0] = 1;
For(i, 1, n) pow2[i] = pow2[i - 1] * 2 % mod;
}
void Add(int & a, int b) {
a += b;
if(a > mod) a -= mod;
}
int main() {
scanf("%d%d", &n, &p), pre(n);
For(i, 1, n) scanf("%d", &c[i]);
if(c[1] == 1 || c[1] == -1) dp[1][1][1][0] += 1;
if(c[1] == 0 || c[1] == -1) dp[1][0][0][1] += 1;
For(i, 1, n - 1) {
For(blk_tot, 0, i) {
wht_tot = i - blk_tot;
For(blk_odd, 0, blk_tot) {
blk_even = blk_tot - blk_odd;
For(wht_odd, 0, wht_tot) {
wht_even = wht_tot - wht_odd;
now = dp[i][blk_tot][blk_odd][wht_odd];
if((c[i + 1] == 1 || c[i + 1] == -1)) {
if(!wht_odd) Add(dp[i + 1][blk_tot + 1][blk_odd + 1][wht_odd], now * pow2[blk_tot + wht_even] % mod);
else {
Add(dp[i + 1][blk_tot + 1][blk_odd + 1][wht_odd], (now * pow2[wht_odd - 1] % mod) * pow2[blk_tot + wht_even] % mod);
Add(dp[i + 1][blk_tot + 1][blk_odd][wht_odd], (now * pow2[wht_odd - 1] % mod) * pow2[blk_tot + wht_even] % mod);
}
}
if(c[i + 1] == 0 || c[i + 1] == -1) {
if(!blk_odd) Add(dp[i + 1][blk_tot][blk_odd][wht_odd + 1], now * pow2[blk_even + wht_tot] % mod);
else {
Add(dp[i + 1][blk_tot][blk_odd][wht_odd + 1], (now * pow2[blk_odd - 1] % mod) * pow2[blk_even + wht_tot] % mod);
Add(dp[i + 1][blk_tot][blk_odd][wht_odd], (now * pow2[blk_odd - 1] % mod) * pow2[blk_even + wht_tot] % mod);
}
}
}
}
}
}
For(i, 0, n) For(j, 0, n) For(k, 0, n) {
if(((j + k) & 1) == p) {
Add(ans, dp[n][i][j][k]);
//printf("%d %d %d %d : %d\n", n, i, j, k, dp[n][i][j][k]);
}
}
printf("%d", ans);
return 0;
}
#include
#include
#include
#include
#define LL long long
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int maxn = 55;
const int mod = 1e9 + 7;
int dp[maxn][maxn][maxn][maxn], now, ans;
int n, p, c[maxn], wht_tot, blk_even, wht_even, rw;
LL C[maxn][maxn], pow2[maxn];
void pre(int n) {
C[0][0] = 1;
For(i, 1, n) For(j, 0, i)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
pow2[0] = 1;
For(i, 1, n) pow2[i] = pow2[i - 1] * 2 % mod;
}
void Add(int & a, int b) {
a += b;
if(a > mod) a -= mod;
}
int main() {
scanf("%d%d", &n, &p), pre(n);
For(i, 1, n) scanf("%d", &c[i]);
if(c[1] == 1 || c[1] == -1) dp[1][1][1][0] += 1;
if(c[1] == 0 || c[1] == -1) dp[1][0][0][1] += 1;
For(i, 1, n - 1) {
For(blk_tot, 0, i) {
wht_tot = i - blk_tot;
For(blk_odd, 0, blk_tot) {
blk_even = blk_tot - blk_odd;
For(wht_odd, 0, wht_tot) {
wht_even = wht_tot - wht_odd;
now = dp[i][blk_tot][blk_odd][wht_odd];
if(c[i + 1] == 1 || c[i + 1] == -1) {
rw = 0;
For(to_wht_odd, 0, wht_odd) {
if(!rw) Add(dp[i + 1][blk_tot + 1][blk_odd + 1][wht_odd], (now * C[wht_odd][to_wht_odd] % mod) * pow2[blk_tot + wht_even] % mod);
else Add(dp[i + 1][blk_tot + 1][blk_odd][wht_odd], (now * C[wht_odd][to_wht_odd] % mod) * pow2[blk_tot + wht_even] % mod);
rw ^= 1;
}
}
if(c[i + 1] == 0 || c[i + 1] == -1) {
rw = 0;
For(to_blk_odd, 0, blk_odd) {
if(!rw) Add(dp[i + 1][blk_tot][blk_odd][wht_odd + 1], (now * C[blk_odd][to_blk_odd] % mod) * pow2[blk_even + wht_tot] % mod);
else Add(dp[i + 1][blk_tot][blk_odd][wht_odd], (now * C[blk_odd][to_blk_odd] % mod) * pow2[blk_even + wht_tot] % mod);
rw ^= 1;
}
}
}
}
}
}
For(i, 0, n) For(j, 0, n) For(k, 0, n) {
if(((j + k) & 1) == p) {
Add(ans, dp[n][i][j][k]);
//printf("%d %d %d %d : %d\n", n, i, j, k, dp[n][i][j][k]);
}
}
printf("%d", ans);
return 0;
}
没有帐号? 立即注册