题目链接
Solution
据信这是一类经典的用矩阵快速幂优化 $dp$ 的题目，学到了。
首先有一个显然的 $dp$：设 $dp[i][r][j]$ 表示已填前 $i$ 位、末尾与字符串 $k$ 匹配了 $j$ 位，当前模 $11$ 等于 $r$ 的方案数。那么转移就是：
其中 $x$ 是填在第 $i+1$ 位的数，$f(j,x)$ 是计算在匹配了 $j$ 位的情况下填上 $x$ 之后最多能匹配到的地方，可以用 fail 数组搞定。
但是直接转移是 $O(10\times 6\times 11\times n)\approx O(6.6e8)$，会超时。
然后这玩意儿可以矩阵快速幂优化，为了看的更清楚，我们可以滚掉 $dp$ 数组的第一维，然后发现，$dp$ 数组的转移是固定的，所以可以用矩阵表示出来。具体地说，由于 $(r,j)$ 能转移到 $((10r+x)\bmod 11,f(j,x))$，所以我们就在系数矩阵的第 $((10r+x)\bmod 11,f(j,x))$ 行第 $(r,j)$ 列加上 $1$（当然这里要把 $(r,j)$ 两个维度压扁成一个，按住不表），如此，前一个 $dp$ 数组乘上该矩阵就得到了后一个 $dp$ 数组。现在我就可以矩阵快速幂了。
计算答案的时候，用所有可能性 $10^n$ 减去不合法的数量 $\sum\limits_{r=1}^{10}\sum\limits_{j=0}^{lenk-1}dp[(r,j)]$，记得特判 $10^n$ 这个数。
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
95
| #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 998244353;
struct Matrix{
int n;
LL a[105][105];
Matrix(){ memset(a, 0, sizeof a); }
void eye(){
memset(a, 0, sizeof a);
for(int i = 1; i <= n; i++) a[i][i] = 1;
}
Matrix operator * (const Matrix &A) const{
Matrix c; c.n = n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
for(int k = 1; k <= n; k++)
(c.a[i][j] += a[i][k] * A.a[k][j] % MOD) %= MOD;
return c;
}
};
Matrix fpow(Matrix bs, LL idx){
Matrix res;
res.n = bs.n; res.eye();
while(idx){
if(idx & 1) res = res * bs;
bs = bs * bs;
idx >>= 1;
}
return res;
}
int n, lenk;
char k[200005];
int fail[105];
void getFail(char t[], int lent){
int i = 1, j = 0;
fail[1] = 0;
while(i <= lent){
if(!j || t[i] == t[j]){
i++, j++;
if(t[i] != t[j]) fail[i] = j;
else fail[i] = fail[j];
}
else j = fail[j];
}
}
inline int f(int j, int x){
j++;
while(j && (k[j] != x+'0'))
j = fail[j];
return j;
}
inline int get(int x, int y){ return x * (lenk + 1) + y + 1; }
int main(){
int T; for(scanf("%d", &T); T; T--){
memset(fail, 0, sizeof fail);
scanf("%d%s", &n, k+1);
lenk = strlen(k+1);
getFail(k, lenk);
Matrix mat;
mat.n = 100;
for(int j = 0; j < lenk; j++){
for(int x = 0; x <= 9; x++){
int g = f(j, x);
if(g == lenk) continue;
for(int r = 0; r < 11; r++)
(mat.a[get((r*10+x)%11, g)][get(r, j)] += 1) %= MOD;
}
}
mat = fpow(mat, n);
LL ans = 1;
for(int i = 1; i <= n; i++) (ans *= 10) %= MOD;
for(int r = 1; r < 11; r++)
for(int j = 0; j < lenk; j++)
(ans -= mat.a[get(r, j)][1]) %= MOD;
bool extra = (k[1] == '1');
for(int i = 2; i <= lenk; i++)
extra &= (k[i] == '0');
extra &= (n >= lenk - 1);
ans += extra;
ans = (ans % MOD + MOD) % MOD;
printf("%lld\n", ans);
}
return 0;
}
|