DDOSvoid's Blog

CF 1608D Dominoes(多项式)

发表于 分类于
本文字数： 6.9k 阅读时长 ≈ 6 分钟

题目描述

https://codeforces.com/contest/1608/problem/D

简要题意：现在有 $n$ 个骨牌，每个骨牌有左右两边，每边只能是黑色和白色且不能交换，现在给定 $n$ 个骨牌，有些骨牌的的某一些边已经固定了颜色，剩下的位置需要你来染色，现在一种合法的染色方案为将 $n$ 个骨牌染好色之后，存在一个圆排列满足，任亮两个相邻骨牌的相邻的两个边的颜色不同，即第 $i$ 个骨牌的右边和第 $i+1$ 个骨牌的左边的颜色不同，求有多少种染色方案

$n\le 10^5$

Solution

容易得到一个合法方案一定有 $00$ 和 $11$ 的数量相同，但如果 $00$ 和 $11$ 都只出现一次，会有一些不合法方案，这个单独处理即可，所以接下来的讨论我们不考虑这种情况

我们令 $a$ 表示 $00$ 的个数，$b$ 表示 $11$ 的个数，$c$ 表示 $0?$ 加上 $?0$ 个数，$d$ 表示 $1?$ 加上 $?1$ 的个数，$e$ 表示 $??$ 个数

令 $f_{i}$ 表示 $00$ 的个数减掉 $11$ 的个数为 $i$ 的染色方案数

容易得到一个 $c$ 会让 $f’_i= f_i+f_{i-1}$，一个 $d$ 会让 $f’_i=f_i+f_{i+1}$，一个 $e$ 会让 $f’_i=f_{i-1}+2f_i+f_{i+1}$，这个东西是线性变换，我们考虑多项式，第一个相当于乘上 $(1+x)^c$，第二个相当于乘上 $(1+\frac{1}{x})^d$，第三个相当于乘上 $(2+x+\frac{1}{x})$，除了第三个，前面两个的式子我们都可以手推出来，第三个我们只能做多项式快速幂了

时间复杂度为 $O(n\log 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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <set>
#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;
}

#define Poly vector<int>
#define len(A) ((int) A.size())
namespace Pol {
    inline int add(int a, int b) { return (a += b) >= p ? a -= p : a; }
    inline int mul(int a, int b) { return 1ll * a * b % p; } 
    Poly operator - (const int &v, const Poly &a) {
        Poly res(a); 
        for (int i = 0; i < len(res); ++i) res[i] = p - res[i]; 
        res[0] = add(res[0], v); return res;
    }
    Poly operator - (const Poly &a, const int &v) {
        Poly res(a); res[0] = add(res[0], p - v); return res;
    }
    Poly operator * (const Poly &a, const int &v) {
        Poly res(a);
        for (int i = 0; i < len(res) ; ++i) res[i] = mul(res[i], v); 
        return res;
    }
 
    const int N = 4200000;
    int P[N];
    void init_P(int n) {
        int l = 0; while ((1 << l) < n) ++l;
        for (int i = 0; i < n; ++i) P[i] = (P[i >> 1] >> 1) | ((i & 1) << l - 1);
    }
    void NTT(Poly &a, int type) {
        static int w[N]; ll G = 3, Gi = pow_mod(G, p - 2); int n = len(a);
        for (int i = 0; i < n; ++i) if (i < P[i]) swap(a[i], a[P[i]]);
        for (int i = 2, m = 1; i <= n; m = i, i *= 2) {
            ll wn = pow_mod(type > 0 ? G : Gi, (p - 1) / i);
            w[0] = 1; for (int j = 1; j < m; ++j) w[j] = wn * w[j - 1] % p;
            for (int j = 0; j < n; j += i)
                for (int k = 0; k < m; ++k) {
                    int t1 = a[j + k], t2 = 1ll * a[j + k + m] * w[k] % p;
                    a[j + k] = add(t1, t2);
                    a[j + k + m] = add(t1, p - t2);
                }
        }
        if (type < 0) {
            int inv = pow_mod(n, p - 2);
            for (int i = 0; i < n; ++i) a[i] = mul(a[i], inv);
        }
    }
    Poly operator * (const Poly &A, const Poly &B) {
        int n = 1, n1 = len(A), n2 = len(B); while (n < n1 + n2 - 1) n <<= 1; init_P(n);
        Poly a(n), b(n);
        for (int i = 0; i < n1; ++i) a[i] = add(A[i], p);
        for (int i = 0; i < n2; ++i) b[i] = add(B[i], p);
        NTT(a, 1); NTT(b, 1);
        for (int i = 0; i < n; ++i) a[i] = mul(a[i], b[i]);
        NTT(a, -1); return a; 
    }
    Poly Der(const Poly &a) {
        Poly res(a);
        for (int i = 0; i < len(a) - 1; ++i) res[i] = mul(i + 1, res[i + 1]);
        res[len(a) - 1] = 0; return res;
    }
    Poly Int(const Poly &a) {
        static int inv[N];
        if (!inv[1]) {
            inv[1] = 1; 
            for (int i = 2; i < N; ++i) inv[i] = mul(p - p / i, inv[p % i]);
        }
        Poly res(a); res.resize(len(a) + 1);
        for (int i = len(a); i; --i) res[i] = mul(res[i - 1], inv[i]);
        res[0] = 0; return res;
    }
    Poly Inv(const Poly &a) {
        Poly res(1, pow_mod(a[0], p - 2)); 
        int n = 1; while (n < len(a)) n <<= 1; 
        for (int k = 2; k <= n; k <<= 1) {
            int L = 2 * k; init_P(L); Poly t(L);
            copy_n(a.begin(), min(k, len(a)), t.begin()); 
            t.resize(L); res.resize(L);
            NTT(res, 1); NTT(t, 1);
            for (int i = 0; i < L; ++i) res[i] = mul(res[i], add(2, p - mul(t[i], res[i])));
            NTT(res, -1); res.resize(k);
        } res.resize(len(a)); return res;
    }
    pair<Poly, Poly> Divide(const Poly &a, const Poly &b) {
        int n = len(a), m = len(b); 
        Poly t1(a.rbegin(), a.rbegin() + n - m + 1), t2(b.rbegin(), b.rend()); t2.resize(n - m + 1);
        Poly Q = Inv(t2) * t1; Q.resize(n - m + 1); reverse(Q.begin(), Q.end());
        Poly R = Q * b; R.resize(m - 1); for (int i = 0; i < len(R); ++i) R[i] = add(a[i], p - R[i]);
        return make_pair(Q, R); 
    }
    Poly Ln(const Poly &a) {
        Poly res = Int(Der(a) * Inv(a));
        res.resize(len(a)); return res;
    }
    Poly Exp(const Poly &a) {
        Poly res(1, 1);
        int n = 1; while (n < len(a)) n <<= 1;
        for (int k = 2; k <= n; k <<= 1) {
            Poly t(res.begin(), res.end()); t.resize(k); t = Ln(t);
            for (int i = 0; i < min(len(a), k); ++i) t[i] = add(a[i], p - t[i]); t[0] = add(t[0], 1);
            res = res * t; res.resize(k);
        } res.resize(len(a)); return res;
    }
    Poly Sqrt(const Poly &a) { // a[0] = 1
        Poly res(1, 1); ll inv2 = pow_mod(2, p - 2); 
        int n = 1; while (n < len(a)) n <<= 1;
        for (int k = 2; k <= n; k <<= 1) {
            Poly t(res.begin(), res.end()), ta(a.begin(), a.begin() + min(len(a), k));
            t.resize(k); t = Inv(t) * ta; 
            res.resize(k); for (int i = 0; i < k; ++i) res[i] = mul(add(res[i], t[i]), inv2);
        } res.resize(len(a)); return res;
    }
    Poly Pow(const Poly &a, int k) { // a[0] = 1
        return Exp(Ln(a) * k);
    }
    Poly Pow(const Poly &a, int k, int kk) { 
        int n = len(a), t = n, m, v, inv, powv; Poly res(n);
        for (int i = n - 1; ~i; --i) if (a[i]) t = i, v = a[i];
        if (k && t >= (n + k - 1) / k) return res;
        if (t == n) { if (!k) res[0] = 1; return res; }
        m = n - t * k; res.resize(m);
        inv = pow_mod(v, p - 2); powv = pow_mod(v, kk); 
        for (int i = 0; i < m; ++i) res[i] = mul(a[i + (k > 0) * t], inv);
        res = Exp(Ln(res) * k); res.resize(n); 
        for (int i = m - 1; ~i; --i) {
            ll tmp = mul(res[i], powv);
            res[i] = 0, res[i + t * k] = tmp;
        }
        return res;
    }
}  // namespace Pol

int n, a, b, c, d, e, f, g;

ll fac[maxn], inv[maxn];
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 || m < 0) ? 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(n); 
    for (int i = 1; i <= n; ++i) {
        char s[10]; cin >> s;
        if (s[0] == '?' && s[1] == '?') ++e;
        else if (s[0] == '?' && s[1] == 'W' || s[0] == 'W' && s[1] == '?') {
            if (s[0] == '?') f = 1;
            else g = 1; 
            ++c;
        }
        else if (s[0] == '?' && s[1] == 'B' || s[0] == 'B' && s[1] == '?') {
            if (s[0] == '?') f = 1;
            else g = 1; 
            ++d;
        }
        else if (s[0] == 'W' && s[1] == 'W') ++a;
        else if (s[0] == 'B' && s[1] == 'B') ++b;
        else if (s[0] == 'B' && s[1] == 'W') f = 1;
        else if (s[0] == 'W' && s[1] == 'B') g = 1; 
    } int k = n + a - b, len = 2 * n + 1; Poly A(len), B(len); A[k] = 1; 
    
    for (int i = 0; i <= c; ++i) B[i] = C(c, i); 
    A = Pol::operator*(A, B); A.resize(len);

    for (int i = 0; i < len; ++i) B[i] = 0; 
    for (int i = 0; i <= d; ++i) B[i] = C(d, i);
    A = Pol::operator*(A, B);
    for (int i = 0; i + d < A.size(); ++i) A[i] = A[i + d]; A.resize(len);

    B.resize(len); for (int i = 0; i < len; ++i) B[i] = 0; B[0] = B[2] = 1; B[1] = 2; 
    B = Pol::Pow(B, e); A = Pol::operator*(A, B);
    for (int i = 0; i + e < A.size(); ++i) A[i] = A[i + e]; A.resize(len);

    ll ans = A[n];
    if (!a && !b) ans = (ans - pow_mod(2, e) + (!f) + (!g)) % p;
    cout << (ans + p) % p << "\n";
    return 0;
}