题目描述
https://codeforces.com/contest/1608/problem/D
简要题意：现在有 $n$ 个骨牌，每个骨牌有左右两边，每边只能是黑色和白色且不能交换，现在给定 $n$ 个骨牌，有些骨牌的的某一些边已经固定了颜色，剩下的位置需要你来染色，现在一种合法的染色方案为将 $n$ 个骨牌染好色之后，存在一个圆排列满足，任亮两个相邻骨牌的相邻的两个边的颜色不同，即第 $i$ 个骨牌的右边和第 $i+1$ 个骨牌的左边的颜色不同，求有多少种染色方案
$n\le 10^5$
Solution
容易发现对于任意一种合法的染色方案，不考虑左右边，黑色和白色的个数都必须是 $n$，令 $cntb$ 和 $cntw$ 分别表示已经固定的白色和黑色的个数，那么现在我们就有一个方案数 $\binom{2n-cntb-cntw}{n-cntw}$
这里面一定包含了所有合法方案，但有一些方案不合法的，我们考虑什么情况下会出现不合法方案，另外我们注意到我们这样染色 $00$ 和 $11$ 的块一定是一样多的，因为 $cntb=cntw=n$ 且 $01$ 和 $10$ 不影响 $cntb$ 和 $cntw$ 的差值
通过观察我们能够发现，只要 $00$ 和 $11$ 的数量大于等于 $1$，方案就一定是合法的，那么我们只要把 $00$ 和 $11$ 出现 $0$ 次的不合法方案减掉即可
时间复杂度 $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
| #include <iostream>
#define maxn 100010
#define ll long long
using namespace std;
const int p = 998244353;
ll pow_mod(ll x, ll n) {
ll s = 1;
for (; n; n >>= 1, x = x * x % p)
if (n & 1) s = s * x % p;
return s;
}
int n, cntb, cntw;
char s[maxn][2];
ll fac[maxn * 2], inv[maxn * 2];
void init_C(int n) {
fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % p;
inv[n] = pow_mod(fac[n], p - 2); for (int i = n - 1; ~i; --i) inv[i] = inv[i + 1] * (i + 1) % p;
}
ll C(int n, int m) { return n < m ? 0 : fac[n] * inv[m] % p * inv[n - m] % p; }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n; init_C(2 * n);
for (int i = 1; i <= n; ++i) cin >> s[i];
for (int i = 1; i <= n; ++i)
for (int k = 0; k < 2; ++k)
if (s[i][k] == 'B') ++cntb;
else if (s[i][k] == 'W') ++cntw;
if (cntb > n || cntw > n) return cout << 0 << "\n", 0;
ll ans = C(2 * n - cntb - cntw, n - cntb), mul = 1; bool ok = 1, f = 0, g = 0;
for (int i = 1; i <= n; ++i) {
if (s[i][0] == 'W' && s[i][1] == 'W' || s[i][0] == 'B' && s[i][1] == 'B') ok = 0;
if (s[i][0] == 'W' && s[i][1] != 'W' || s[i][0] != 'B' && s[i][1] == 'B') f = 1;
if (s[i][0] == 'B' && s[i][1] != 'B' || s[i][0] != 'W' && s[i][1] == 'W') g = 1;
if (s[i][0] == '?' && s[i][1] == '?') mul = mul * 2 % p;
}
if (ok) ans = (ans - mul + !f + !g) % p;
cout << (ans + p) % p << "\n";
return 0;
}
|