#3098. 「SNOI2019」纸牌
Summarize
有一副纸牌，牌一共有 $n$ 种，每种有 $C$ 张。三张连号的牌或三张相同的牌可以组成一叠，如果一组拍可以分成若干叠，就称其为一组王牌。现已从牌堆摸了一些初始牌，需要再挑出一些牌组成一组王牌，求有多少种可能组成的王牌。
$1\le n \le 1e18,0\le C \le 1000$
Solution
麻将题这种套路我真不明白是怎么想出来的…… 总之能用就行了。
记 $f[i][a][b]$ 表示仅考虑前 $i$ 种牌，选了 $a$ 叠 $(i-1,i,i+1)$ 和 $b$ 叠 $(i,i+1,i+2)$ 的方案数。不难发现 $a$ 和 $b$ 均不超过 $3$，否则会有重复。
状态转移方程如下：
$$
f[i][b][c] = f[i - 1][a][b]\times (\lfloor\frac{C-s-\lceil d[i]-s\rceil}{3}\rfloor+1)
$$
将状态的后两维压至一维，即可矩阵大力转移。对于特殊点构造转移矩阵即可。
Note
动态规划转移前的可行性判断。
矩阵操作前（乘法、初始化单位矩阵）不要忘记清零！
Code
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 998244353;
struct Matrix {
int m, n;
int g[9][9];
};
Matrix mul(Matrix a, Matrix b) {
Matrix c;
c.m = a.m, c.n = b.n;
for (int i = 0; i < c.m; ++i)
for (int j = 0; j < c.n; ++j) {
c.g[i][j] = 0;
for (int k = 0; k < a.n; ++k)
c.g[i][j] = (c.g[i][j] + 1ll * a.g[i][k] * b.g[k][j] % MOD) % MOD;
}
return c;
}
ll n;
int C, x;
void mk(Matrix& a) {
a.m = a.n = 9;
for (int i = 0; i < 9; ++i)
for (int j = 0; j < 9; ++j)
a.g[i][j] = i == j ? 1 : 0;
}
Matrix qpow(Matrix a, ll n) {
Matrix ret;
mk(ret);
while (n) {
if (n & 1) ret = mul(ret, a);
a = mul(a, a);
n >>= 1;
}
return ret;
}
int main() {
scanf("%lld%d", &n, &C);
Matrix X;
X.m = 9, X.n = 1;
X.g[0][0] = 1;
for (int i = 1; i < 9; ++i)
X.g[i][0] = 0;
Matrix F;
F.m = F.n = 9;
for (int i = 0; i < 9; ++i)
for (int j = 0; j < 9; ++j)
F.g[i][j] = 0;
for (int b = 0; b <= 2; ++b)
for (int c = 0; c <= 2; ++c)
for (int a = 0; a <= 2; ++a) {
int s = a + b + c;
if (C < s) continue;
F.g[a * 3 + b][b * 3 + c] = (C - s) / 3 + 1;
}
scanf("%d", &x);
ll cur = 0;
for (int t = 1; t <= x; ++t) {
ll p;
int d;
scanf("%lld%d", &p, &d);
X = mul(qpow(F, p - cur - 1), X);
Matrix G;
G.m = G.n = 9;
for (int i = 0; i < 9; ++i)
for (int j = 0; j < 9; ++j)
G.g[i][j] = 0;
for (int b = 0; b <= 2; ++b)
for (int c = 0; c <= 2; ++c)
for (int a = 0; a <= 2; ++a) {
int s = a + b + c;
if (C < s) continue;
int cer = 0;
if (d <= s) cer = s;
else cer = s + 3 * ((d - s + 2) / 3);
if (C < cer) continue;
G.g[a * 3 + b][b * 3 + c] = (C - cer) / 3 + 1;
}
X = mul(G, X);
cur = p;
}
X = mul(qpow(F, n - cur), X);
printf("%d", X.g[0][0]);
return 0;
}
|