推蒟蒻 $\color{limegreen}{blog}$ ！
原题链接~
题是简单题，重在想到矩乘后怎么往下写。
题意不须讲了，很清楚而且很有意思。
转移方程稍微给一下，推导可以阅读别的题解。
设置状态 $dp_{\ i}$ 指的是：长度为 $i$ 时可行的分块方案。
我们有: （ $x$ 指的是的可能的块长（即两人公认的其中一种块长））
我们看到块总长是 $\leq 1e18$ 的，连 $N$ 的空间都开不下，就别提更高维的数组了。
因为开不下，所以 $O(N)$ 递推难矣。
『递推的优化，显然矩乘。』
我们尽量少算值，整出个初始状态就差不多可以了。
要推第 $i$ 项，要保证在所有可能的块长 $x$ 下，第 $i-x$ 项都已知。
因为块长不会大于 $100$ ，故我们可以先预处理到 $dp_{\ 100}$ 。
开 $100 * 100$ 的矩阵，至少可以保证递推时每一项都能推得出来。
现在就到了矩阵乘法最重要的一部分————初始化矩阵。
目前这一步的状态需要前面哪几步的状态推出？
我们通过递推式知道了，与 $x$ 步前的状态有关系（以下的 $x$ 指代每一种可能的块长）。
我们把 $dp_{\ i}$ 放在原始矩阵的第 $(1,1)$ 位置，那就把 $dp_{\ i-k}$ 放在 $(k,1)$ 位置。
也就是说新的矩阵的 $(1,1)$ 位置，要由所有的 $(x,1)$ 的总和转移而来。
那转移矩阵的第一行里必然有：对于每一个可行的 $x$ ， $(1,x)$ 处为 $1$ ，其余位置为 $0$ 。
比如对于样例1， $1$ 和 $2$ 都是可行的 $x$ ，转移矩阵的第一行必如下图：
我们解决了第一行，那其他行如何处理？
我们此刻的 $dp_{\ i}$ ，在下一次（第 $i-1$ 次）转移后就将成为 $dp_{\ (i+1)-1}$ ，所以应向后推一位，从原来的 $(1,1)$ 位置后推到 $(2,1)$ 位置。
这一过程在做其他矩乘题里必然也经常用到，对于第 $i(i\neq 1)$ 行，我们在 $(i,i-1)$ 位置设为 $1$ ，其余位置设为 $0$ 。
这样可以做到原来在 $(1,1)$ 的第 $dp_{\ i}$ 位在转移后移至 $(1,2)$ 。
对于后面几位亦如此。
最终成品转移矩阵如下（中间省略了一部分数值）：
所以 $AC$ 此题，流程如下：
- 预处理 $dp_{\ 100} $ ，填入原始矩阵。
- 初始化转移矩阵。
- 矩阵快速幂。
- 输出最终答案矩阵的 $(1,1)$ 。
以下是代码～
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
| #include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9 + 7;
int LEN, PR, NF;
map<int, int> m1, m2;
int N;
int dp[107];
struct matrix
{
int num[107][107];
matrix operator*(const matrix a) const
{
matrix c;
memset(c.num, 0, sizeof(c.num));
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
for (int k = 1; k <= N; k++)
{
c.num[i][j] = (c.num[i][j] + (num[i][k] * a.num[k][j]) % MOD) % MOD;
}
}
}
return c;
}
} ORZ, RBQ;
matrix quick_pow(matrix a, int p)
{
if (p == 1)
{
return a;
}
matrix tmp = quick_pow(a, p / 2);
if (p % 2 == 0)
{
return tmp * tmp;
}
else
{
return tmp * tmp * a;
}
}
signed main()
{
memset(ORZ.num, 0, sizeof(ORZ.num));
memset(RBQ.num, 0, sizeof(RBQ.num));
cin >> LEN;
cin >> PR;
for (int i = 1; i <= PR; i++)
{
int num;
cin >> num;
m1[num] = 1;
}
cin >> NF;
for (int i = 1; i <= NF; i++)
{
int num;
cin >> num;
if (m1[num])
{
m2[num] = 1;
}
}
for (int i = 1; i <= 100; i++)
{
if (m2[i] == 1)
{
RBQ.num[1][i] = 1;
N = i;
}
}
for (int i = 1; i < N; i++)
{
RBQ.num[i + 1][i] = 1;
}
dp[0] = 1;
for (int i = 1; i < N; i++)
{
for (int j = 1; j <= i; j++)
{
if (m2[j] == 1)
{
dp[i] = (dp[i] + dp[i - j]) % MOD;
}
}
ORZ.num[N - i][1] = dp[i];
}
ORZ.num[N][1] = 1;
matrix ans = quick_pow(RBQ, LEN - N + 1) * ORZ;
cout << ans.num[1][1];
}
|
