【泛做】矩阵加速转移

大概是整理“[HNOI2008]GT考试”和“[SNOI2017]礼物”两道题。由于实在找不出什么共同点来,所以就随便找了个理由把两道题放在一起了233

从各个角度来看,都算是比较妙的设计方式了?

[HNOI2008]GT考试

求 $n$ 位数字串不连续包括某个长度为 $m$ 的数字串的方案数。

$n\leq 10^9,m\leq 20$

考虑直接 $dp$ 。个人认为这个地方还是有一点 trivial 的。首先就是考虑一种状态设计,记 $f_{i,j}$ 表示长串匹配到第 $i$ 位,短串匹配到第 $j$ 位的合法方案数。那么考虑可以转移:

其中 $o=0\sim j-1$,取决于怎么个失配法。这样转移似乎并不可以。于是考虑另一种方式转移

其中 $g_{x,y}$ 表示现在已经匹配到了第 $x$ 位,有多少种方案使得在加了一个数字后变成匹配到 $y$ 位的方案数。

发现本质上这就是在做一个 KMP。于是可以用 KMP 预处理处这样的一张数表 $\{g\}$ 。同时,发现对于原来的式子,右边的 $g$ 不变,且转移方式就是矩阵的转移方式,于是考虑直接用矩阵优化掉。最终复杂度 $m^3\log n$。

btw,由于本质上转移已经写在那里了,所以不用费劲去构造一个矩阵了…wsdd

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
int ans ;
int fail[N] ;
int n, m, p ;

struct Matrix{
int M[N][N] ;
void clear(){
memset(M, 0, sizeof(M)) ;
}
void reset(){
clear() ;
for (int i = 0 ; i < N ; ++ i) M[i][i] = 1 ;
}
Matrix friend operator * (const Matrix &a, const Matrix &b){
Matrix ans ; ans.clear() ;
for (int i = 0 ; i < N ; ++ i)
for (int j = 0 ; j < N ; ++ j)
for (int k = 0 ; k < N ; ++ k)
(ans.M[i][j] += a.M[i][k] * b.M[k][j] % p) %= p ;
return ans ;
}
Matrix friend operator ^ (Matrix a, int b){
Matrix res ; res.reset() ;
while (b){
if (b & 1)
res = res * a ;
a = a * a ; b >>= 1 ;
}
return res ;
}
} g ;

int main(){
cin >> n >> m >> p ; scanf("%s", s + 1) ;
for (int i = 2, j = 0 ; i <= m ; ++ i){
while (j && s[j + 1] != s[i]) j = fail[j] ;
if (s[j + 1] == s[i]) ++ j ; fail[i] = j ;
}
for (int j = 0, i = 0 ; i < m ; j = ++ i)
for (int c = '0' ; c <= '9' ; j = i, ++ c){
while (j && (int)s[j + 1] != c) j = fail[j] ;
if ((int)s[j + 1] == c) ++ j ; g.M[i][j] ++ ;
}
g = g ^ n ;
for (int i = 0 ; i < m ; ++ i)
(ans += g.M[0][i]) %= p ;
return cout << ans << endl, 0 ;
}

[SNOI2017]礼物

给定 $k$,设 $f_i$ 的递推式如下:

$k\leq 500,n\leq 10^{18}$

当然这题有什么其余的大力多项式算法,复杂度是什么 $O(k+\log n)$ 的…要知道原原本本这题 $k$ 只有 $10$ 这么大啊/kk

考虑先设 $s_n=\sum_{i=1}^nf_i$ ,那么发现

于是发现可以递推 $s_n$。那么发现这个地方有一个常系数 $n^k$,尝试依靠

这个东西来得到,即

然后就可以愉快地矩乘了。

不过似乎有个性质值得注意,就是本身这个转移矩阵就是一个上三角的形式,所以可能会存在什么有趣的东西…不得而知不得而知…

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 <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define MAK 43
#define ll long long
#define Mod 1000000007

using namespace std ;
ll N, K, Ans, T, C[MAK][MAK];

inline ll expow(long long x, int y){
ll res = 1 ; x %= Mod ;
while (y){
if (y & 1) res = res * x % Mod ;
x = x * x % Mod, /* pks */ y >>= 1 ;
}
return res ;
}
inline ll Solve1(){
int i ;
for (i = 1 ; i <= N ; ++ i)
Ans = (T + expow(i, K)) % Mod, T = (T + Ans) % Mod ;
return Ans ;
}
namespace Ma{
int i, j, k ;
struct Matrix{
int M[50][50] ;
inline void clear(){ memset(M, 0, sizeof(M)) ; }
inline void reset(){ clear() ; for(i = 1 ; i <= K + 1 ; ++ i) M[i][i] = 1 ; }
Matrix friend operator *(const Matrix&A, const Matrix &B){
Matrix Ans ; Ans.clear() ; int P = K + 2 ;
for (int i = 1 ; i <= P ; ++ i)
for (int j = 1 ; j <= P ; ++ j)
for (int k = 1 ; k <= P ; ++ k)
Ans.M[i][j] = (Ans.M[i][j] + 1ll * A.M[i][k] * B.M[k][j] % Mod ) % Mod ;
return Ans ;
}
Matrix friend operator +(const Matrix&A, const Matrix &B){
Matrix Ans ; Ans.clear() ;
for (int i = 1 ; i <= K + 2 ; ++ i)
for (int j = 1 ; j <= K + 2 ; ++ j)
Ans.M[i][j] = (A.M[i][j] + B.M[i][j]) % Mod ;
return Ans ;
}
}P, Ans ; int C[MAK][MAK] ;
inline void Init(){
P.M[1][1] = 2, C[0][0] = 1 ;
for (i = 0 ; i <= K + 2 ; ++ i) C[i][0] = 1 ;
for (i = 1 ; i <= K + 2 ; ++ i)
for (j = 1 ; j <= K + 2 ; ++ j)
C[i][j] = (1ll * C[i - 1][j] + 1ll * C[i - 1][j - 1]) % Mod ;
for (i = 1 ; i <= K + 2 ; ++ i) P.M[1][i + 1] = C[K][i - 1] ;
for (i = 2 ; i <= K + 2 ; ++ i)
for (j = i ; j <= K + 2 ; ++ j)
P.M[i][j] = C[K + 2 - i ][j - i] ;

for (i = K + 2 ; i >= 1 ; -- i) Ans.M[i][1] = 1 ;
}
inline Matrix expow(Matrix x, long long y){
Matrix res ; res.reset() ;
while (y){
if (y & 1) res = res * x ;
x = x * x, /*pkspkspks*/ y >>= 1 ;
}
return res ;
}
inline int expow(int x, int y){
int res = 1 ;
while (y){
if (y & 1) res = 1ll * res * x % Mod ;
x = 1ll * x * x % Mod, /*pkspkspks*/ y >>= 1 ;
}
return res ;
}
inline int Solve2(){
P.clear() ; Init() ;
Matrix A1, A2, N1, N2 ;
N1 = expow(P, N - 2), N2 = N1 * P ; /*
for (i = 1 ; i <= K + 2 ; ++ i, cout << endl)
for (j = 1 ; j <= K + 2 ; ++ j)
cout << P.M[i][j] << " " ; */
// Matrix t = Ans * P ;
A1 = N1 * Ans, A2 = N2 * Ans ;
return (A2.M[1][1] - A1.M[1][1] + Mod) % Mod ;
}
}
int main(){
cin >> N >> K ;
if (N <= 1000000) cout << Solve1() ;
else cout << (Ma :: Solve2()) << endl ; return 0 ;
}

唉,比人会的我都不会,没有前途啊。