Chuyên đề nâng cao 2: Lũy thừa ma trận trong C++ và Python: nhân ma trận, Fibonacci thứ n với n tới 10^18, truy hồi tuyến tính, đếm đường đi độ dài k
Lời mở đầu
Ở bài 19 (quy hoạch động) em đã đếm số cách leo cầu thang, số cách lát gạch, số xâu nhị phân hợp lệ bằng một vòng for từ 1 tới $n$. Ở bài 26 (toán modulo) em đã học lũy thừa nhanh: tính $a^b \bmod p$ với $b = 10^{18}$ chỉ bằng khoảng 60 vòng lặp. Đề thi HSG tỉnh và chuyên Tin rất hay “ghép” hai thứ đó lại: bài QHĐ quen thuộc nhưng $n$ tới $10^{18}$, vòng for chạy tới tận thế kỷ sau cũng chưa xong.
Chìa khoá là nhận ra: mỗi bước QHĐ chỉ là nhân vector trạng thái với một ma trận cố định. Mà phép nhân ma trận có tính kết hợp, nên $n$ bước nhân liên tiếp gộp lại thành $M^n$, và $M^n$ tính được bằng đúng thuật toán lũy thừa nhanh em đã biết. Chuyên đề này dạy em làm việc đó từ đầu tới cuối: nhân ma trận, lũy thừa ma trận, cách dựng ma trận chuyển cho mọi công thức truy hồi tuyến tính, và ứng dụng đẹp nhất: đếm đường đi độ dài $k$ trên đồ thị (đã gặp đồ thị ở bài 21).
Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Nhân ma trận
Ma trận cỡ $n \times m$ đơn giản là một mảng hai chiều $n$ hàng, $m$ cột (em đã dùng ở bài 7). Cho $A$ cỡ $n \times m$ và $B$ cỡ $m \times p$ (số cột của $A$ phải bằng số hàng của $B$), tích $C = A \cdot B$ là ma trận cỡ $n \times p$ với
$C[i][j] = \sum_{t=0}^{m-1} A[i][t] \cdot B[t][j]$.
Nói bằng lời: ô $C[i][j]$ lấy hàng $i$ của $A$ và cột $j$ của $B$, nhân từng cặp phần tử tương ứng rồi cộng lại. Ví dụ $\begin{pmatrix}1 & 2 \\ 3 & 4\end{pmatrix} \cdot \begin{pmatrix}5 & 6 \\ 7 & 8\end{pmatrix} = \begin{pmatrix}19 & 22 \\ 43 & 50\end{pmatrix}$, vì ô góc trên trái là $1 \cdot 5 + 2 \cdot 7 = 19$, ô góc trên phải là $1 \cdot 6 + 2 \cdot 8 = 22$, v.v.
Em bấm Tiếp để xem từng ô của $C$ được tính ra sao, rồi thử nhập ma trận khác (kể cả ma trận không vuông):
Độ phức tạp. $C$ có $n \cdot p$ ô, mỗi ô tốn $m$ phép nhân, tổng $O(n \cdot m \cdot p)$. Trong chuyên đề này ta chủ yếu nhân hai ma trận vuông cỡ $k \times k$, tốn $O(k^3)$: $k = 2$ chỉ 8 phép nhân, $k = 100$ là $10^6$ phép.
Hai tính chất quan trọng của phép nhân ma trận:
- Có tính kết hợp: $(A \cdot B) \cdot C = A \cdot (B \cdot C)$. Nhờ vậy $M \cdot M \cdot \ldots \cdot M$ ($n$ lần) muốn gộp theo thứ tự nào cũng được, và đó chính là thứ lũy thừa nhanh cần.
- Không giao hoán: thường $A \cdot B \ne B \cdot A$. Ví dụ trên đổi chỗ thì $\begin{pmatrix}5 & 6 \\ 7 & 8\end{pmatrix} \cdot \begin{pmatrix}1 & 2 \\ 3 & 4\end{pmatrix} = \begin{pmatrix}23 & 34 \\ 31 & 46\end{pmatrix}$, khác hẳn. Khi code em phải giữ đúng thứ tự nhân.
Ma trận đơn vị $I$ (đường chéo bằng 1, còn lại bằng 0) đóng vai số 1: $I \cdot X = X \cdot I = X$. Ta quy ước $M^0 = I$.
Xem code C++ / Python: nhân hai ma trận (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
long long A[105][105], B[105][105], C[105][105];
int main(){
int n, m, p;
cin >> n >> m >> p; // A cỡ n x m, B cỡ m x p
for(int i = 0; i < n; i++)
for(int t = 0; t < m; t++) cin >> A[i][t];
for(int t = 0; t < m; t++)
for(int j = 0; j < p; j++) cin >> B[t][j];
for(int i = 0; i < n; i++)
for(int j = 0; j < p; j++){
C[i][j] = 0;
for(int t = 0; t < m; t++) // hàng i của A "nhân" cột j của B
C[i][j] += A[i][t] * B[t][j];
}
for(int i = 0; i < n; i++){
for(int j = 0; j < p; j++) cout << C[i][j] << " ";
cout << "\n";
}
return 0;
}import sys
data = sys.stdin.read().split()
n, m, p = int(data[0]), int(data[1]), int(data[2])
vals = list(map(int, data[3:]))
A = [vals[i * m:(i + 1) * m] for i in range(n)]
off = n * m
B = [vals[off + t * p: off + (t + 1) * p] for t in range(m)]
cols = list(zip(*B)) # các cột của B
C = [[sum(x * y for x, y in zip(row, col)) for col in cols] for row in A]
for row in C:
print(*row)A[i][t] * B[t][j] nhỏ hơn $p^2 \approx 10^{18}$, vừa đủ chứa trong long long (tối đa khoảng $9{,}2 \cdot 10^{18}$). Nhưng cộng dồn hai tích là có thể vượt! Vì vậy hãy lấy dư sau mỗi lần cộng: C[i][j] = (C[i][j] + A[i][t] * B[t][j]) % MOD;. Một lỗi rất hay gặp nữa là để phần tử ban đầu âm hoặc $\ge p$ (ví dụ hệ số $-1$): phải đưa về đoạn $[0, p)$ trước khi nhân.Phần 2Lũy thừa nhanh ma trận
Cần tính $M^n$ với $M$ là ma trận vuông $k \times k$ và $n$ có thể tới $10^{18}$. Nhân lần lượt $n$ lần thì không bao giờ xong. Nhưng nhớ lại lũy thừa nhanh ở bài 26: viết $n$ ra hệ nhị phân, ví dụ $13 = 1101_2 = 8 + 4 + 1$, thì $M^{13} = M^{8} \cdot M^{4} \cdot M^{1}$. Các lũy thừa $M^1, M^2, M^4, M^8, \ldots$ có được bằng cách bình phương liên tục. Thuật toán y hệt bản cho số, chỉ thay hai chỗ:
res = 1thànhres = I(ma trận đơn vị);- phép nhân hai số thành phép nhân hai ma trận (hàm
mulở phần 1, có lấy dư).
Vì phép nhân ma trận có tính kết hợp nên ghép các $M^{2^i}$ lại theo thứ tự nào cũng ra đúng $M^n$ (và các lũy thừa của cùng một ma trận thì nhân với nhau giao hoán được, nên ta không lo thứ tự). Số vòng lặp là số bit của $n$, khoảng $\log_2 n$; mỗi vòng tối đa 2 phép nhân ma trận $O(k^3)$. Tổng cộng $O(k^3 \log n)$: với $k = 2$, $n = 10^{18}$ chỉ khoảng $2 \cdot 60 \cdot 8 \approx 1000$ phép nhân số.
| Bit i | Bit của 13 | P = $M^{2^i}$ | Nhân vào res? | res |
|---|---|---|---|---|
| 0 | 1 | $\begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}$ | ✔ có | $M^1 = \begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}$ |
| 1 | 0 | $M^2 = \begin{pmatrix}2 & 1 \\ 1 & 1\end{pmatrix}$ | ✘ không | $M^1$ |
| 2 | 1 | $M^4 = \begin{pmatrix}5 & 3 \\ 3 & 2\end{pmatrix}$ | ✔ có | $M^5 = \begin{pmatrix}8 & 5 \\ 5 & 3\end{pmatrix}$ |
| 3 | 1 | $M^8 = \begin{pmatrix}34 & 21 \\ 21 & 13\end{pmatrix}$ | ✔ có | $M^{13} = \begin{pmatrix}377 & 233 \\ 233 & 144\end{pmatrix}$ |
Bảng 1. Tính $M^{13}$ với $M = \begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}$ (ma trận Fibonacci ở phần 3): chỉ 4 vòng lặp, 6 phép nhân ma trận (3 lần nhân vào res ứng với 3 bit 1, 3 lần bình phương; vòng cuối không bình phương nữa) thay vì 12.
Mô phỏng dưới đây cho em thấy hai ma trận res và P thay đổi qua từng bit. Em thử nhập ma trận $3 \times 3$ và $n$ thật lớn để thấy số phép nhân vẫn rất ít:
Xem code C++ / Python: lũy thừa ma trận k × k (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<long long>> Mat;
const long long MOD = 1000000007;
int k;
Mat mul(const Mat &A, const Mat &B){
Mat C(k, vector<long long>(k, 0));
for(int i = 0; i < k; i++)
for(int t = 0; t < k; t++){
if(A[i][t] == 0) continue;
for(int j = 0; j < k; j++)
C[i][j] = (C[i][j] + A[i][t] * B[t][j]) % MOD;
}
return C;
}
Mat matPow(Mat M, long long n){
Mat res(k, vector<long long>(k, 0));
for(int i = 0; i < k; i++) res[i][i] = 1; // ma trận đơn vị I
while(n > 0){
if(n & 1) res = mul(res, M); // bit 1: nhân M^(2^i) vào res
n >>= 1;
if(n > 0) M = mul(M, M); // còn bit thì mới bình phương: M^(2^i) -> M^(2^(i+1))
}
return res;
}
int main(){
long long n;
cin >> k >> n;
Mat M(k, vector<long long>(k));
for(int i = 0; i < k; i++)
for(int j = 0; j < k; j++){ cin >> M[i][j]; M[i][j] %= MOD; }
Mat R = matPow(M, n);
for(int i = 0; i < k; i++){
for(int j = 0; j < k; j++) cout << R[i][j] << " ";
cout << "\n";
}
return 0;
}import sys
MOD = 10**9 + 7
def mul(A, B):
cols = list(zip(*B)) # các cột của B
return [[sum(x * y for x, y in zip(row, col)) % MOD for col in cols] for row in A]
def mat_pow(M, n):
k = len(M)
res = [[int(i == j) for j in range(k)] for i in range(k)] # ma trận đơn vị I
while n > 0:
if n & 1:
res = mul(res, M) # bit 1: nhân M^(2^i) vào res
n >>= 1
if n > 0: # còn bit thì mới bình phương
M = mul(M, M)
return res
data = sys.stdin.read().split()
k, n = int(data[0]), int(data[1])
vals = [int(x) % MOD for x in data[2:2 + k * k]]
M = [vals[i * k:(i + 1) * k] for i in range(k)]
for row in mat_pow(M, n):
print(*row)Em chạy tay từng dòng để thấy biến M bình phương liên tục (trừ vòng cuối, khi $n$ đã hết bit thì không cần bình phương nữa), còn res chỉ nhận thêm thừa số khi gặp bit 1. Bấm dữ liệu mẫu “n = 0” để kiểm tra trường hợp biên: vòng lặp không chạy lần nào và kết quả là $I$.
Mat matPow(Mat M, long long n){
Mat res = I; // ma trận đơn vị
while(n > 0){
if(n & 1) res = mul(res, M);
n >>= 1;
if(n > 0) M = mul(M, M); // hết bit thì khỏi bình phương
}
return res;
}Phần 3Fibonacci thứ $n$ với $n$ tới $10^{18}$
Dãy Fibonacci: $F(0) = 0$, $F(1) = 1$, $F(n) = F(n-1) + F(n-2)$. Để tính $F(n)$ ta chỉ cần nhớ hai số liên tiếp. Gọi cặp $(F(n), F(n-1))$ là trạng thái tại bước $n$. Từ trạng thái này sang trạng thái kế tiếp $(F(n+1), F(n))$:
$F(n+1) = 1 \cdot F(n) + 1 \cdot F(n-1)$, $F(n) = 1 \cdot F(n) + 0 \cdot F(n-1)$.
Cả hai thành phần mới đều là tổ hợp tuyến tính (nhân hệ số rồi cộng) của thành phần cũ, nên viết được thành phép nhân ma trận với vector cột:
$\begin{pmatrix}F(n+1) \\ F(n)\end{pmatrix} = \begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix} \cdot \begin{pmatrix}F(n) \\ F(n-1)\end{pmatrix}$.
Hàng thứ nhất của ma trận là hệ số của công thức tính $F(n+1)$, hàng thứ hai là hệ số để “chép” $F(n)$ xuống. Đặt $M = \begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}$, áp dụng liên tiếp $n$ lần từ trạng thái đầu $(F(1), F(0)) = (1, 0)$:
$\begin{pmatrix}F(n+1) \\ F(n)\end{pmatrix} = M^n \cdot \begin{pmatrix}1 \\ 0\end{pmatrix}$, và thật ra $M^n = \begin{pmatrix}F(n+1) & F(n) \\ F(n) & F(n-1)\end{pmatrix}$.
Vậy $F(n)$ chính là ô $[0][1]$ của $M^n$. Em kiểm tra lại Bảng 1: $M^{13}$ có ô $[0][1] = 233 = F(13)$, ô $[0][0] = 377 = F(14)$.
Hình 1. Trạng thái là một “cửa sổ” gồm 2 số Fibonacci liên tiếp. Mỗi lần nhân với $M$, cửa sổ trượt sang phải 1 ô. Trượt $n$ lần = nhân $M^n$.
Xem code C++ / Python: Fibonacci thứ n, n ≤ 10^18 (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
struct M2 { ll a, b, c, d; }; // ma trận [[a, b], [c, d]]
M2 mul(M2 x, M2 y){
return { (x.a * y.a + x.b * y.c) % MOD, (x.a * y.b + x.b * y.d) % MOD,
(x.c * y.a + x.d * y.c) % MOD, (x.c * y.b + x.d * y.d) % MOD };
}
int main(){
ll n;
cin >> n;
M2 res = {1, 0, 0, 1}, M = {1, 1, 1, 0}; // res = I, M = ma trận Fibonacci
while(n > 0){
if(n & 1) res = mul(res, M);
M = mul(M, M);
n >>= 1;
}
cout << res.b; // M^n = [[F(n+1), F(n)], [F(n), F(n-1)]]
return 0;
}MOD = 10**9 + 7
def mul(x, y): # ma trận 2x2 lưu dạng (a, b, c, d)
a, b, c, d = x
e, f, g, h = y
return ((a * e + b * g) % MOD, (a * f + b * h) % MOD,
(c * e + d * g) % MOD, (c * f + d * h) % MOD)
n = int(input())
res, M = (1, 0, 0, 1), (1, 1, 1, 0) # res = I, M = ma trận Fibonacci
while n > 0:
if n & 1:
res = mul(res, M)
M = mul(M, M)
n >>= 1
print(res[1]) # M^n = [[F(n+1), F(n)], [F(n), F(n-1)]]struct M2 ở trên chạy nhanh hơn vector<vector> nhiều lần (không cấp phát bộ nhớ). Khi đề có nhiều truy vấn $F(n)$, mỗi truy vấn $O(\log n)$, cách này giúp em không bị quá thời gian. Ngoài ra còn có công thức “nhân đôi”: $F(2m) = F(m)\,(2F(m+1) - F(m))$ và $F(2m+1) = F(m)^2 + F(m+1)^2$, thật ra chính là bình phương ma trận $M^m$ viết gọn lại.Phần 4Truy hồi tuyến tính tổng quát: dựng ma trận chuyển
Fibonacci chỉ là trường hợp riêng. Mọi công thức dạng
$f(n) = c_1 f(n-1) + c_2 f(n-2) + \ldots + c_k f(n-k)$
(gọi là truy hồi tuyến tính bậc $k$) đều giải được bằng lũy thừa ma trận $k \times k$. Trạng thái là $k$ giá trị gần nhất $v(n) = (f(n), f(n-1), \ldots, f(n-k+1))$, và ma trận chuyển $T$ gồm: hàng 0 là các hệ số $c_1, c_2, \ldots, c_k$ (để tính $f(n+1)$); các hàng còn lại có một số 1 ngay dưới đường chéo (để dịch các giá trị cũ xuống một ô):
$\begin{pmatrix}f(n+1) \\ f(n) \\ f(n-1) \\ \vdots \\ f(n-k+2)\end{pmatrix} = \begin{pmatrix}c_1 & c_2 & \cdots & c_{k-1} & c_k \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & & \ddots & & \vdots \\ 0 & 0 & \cdots & 1 & 0\end{pmatrix} \cdot \begin{pmatrix}f(n) \\ f(n-1) \\ f(n-2) \\ \vdots \\ f(n-k+1)\end{pmatrix}$.
Ta biết sẵn $v(k-1) = (f(k-1), \ldots, f(0))$, nên $v(n) = T^{\,n-k+1} \cdot v(k-1)$ và đáp án là thành phần đầu của $v(n)$. Nếu $n < k$ thì in luôn $f(n)$ có sẵn.
Xem code C++ / Python: truy hồi tuyến tính bậc k bằng lũy thừa ma trận (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<long long>> Mat;
const long long MOD = 1000000007;
int k;
Mat mul(const Mat &A, const Mat &B){
Mat C(k, vector<long long>(k, 0));
for(int i = 0; i < k; i++)
for(int t = 0; t < k; t++){
if(A[i][t] == 0) continue;
for(int j = 0; j < k; j++)
C[i][j] = (C[i][j] + A[i][t] * B[t][j]) % MOD;
}
return C;
}
int main(){
long long n;
cin >> k >> n;
vector<long long> c(k), f(k);
for(auto &x : c) cin >> x; // c1..ck
for(auto &x : f) cin >> x; // f(0)..f(k-1)
if(n < k){ cout << f[n] % MOD; return 0; }
Mat T(k, vector<long long>(k, 0));
for(int j = 0; j < k; j++) T[0][j] = c[j] % MOD; // hàng 0: f(n) = c1 f(n-1) + ... + ck f(n-k)
for(int i = 1; i < k; i++) T[i][i - 1] = 1; // các hàng sau: dịch trạng thái xuống 1 ô
Mat R(k, vector<long long>(k, 0));
for(int i = 0; i < k; i++) R[i][i] = 1;
long long e = n - k + 1; // v(n) = T^(n-k+1) . v(k-1)
while(e > 0){
if(e & 1) R = mul(R, T);
T = mul(T, T);
e >>= 1;
}
long long ans = 0; // v(k-1) = (f(k-1), f(k-2), ..., f(0))
for(int j = 0; j < k; j++) ans = (ans + R[0][j] * (f[k - 1 - j] % MOD)) % MOD;
cout << ans;
return 0;
}import sys
MOD = 10**9 + 7
def mul(A, B):
cols = list(zip(*B))
return [[sum(x * y for x, y in zip(row, col)) % MOD for col in cols] for row in A]
def mat_pow(M, e):
k = len(M)
res = [[int(i == j) for j in range(k)] for i in range(k)]
while e > 0:
if e & 1:
res = mul(res, M)
M = mul(M, M)
e >>= 1
return res
data = sys.stdin.read().split()
k, n = int(data[0]), int(data[1])
c = [int(x) % MOD for x in data[2:2 + k]]
f = [int(x) % MOD for x in data[2 + k:2 + 2 * k]]
if n < k:
print(f[n])
else:
T = [[0] * k for _ in range(k)]
T[0] = c[:] # hàng 0: công thức truy hồi
for i in range(1, k):
T[i][i - 1] = 1 # các hàng sau: dịch trạng thái
R = mat_pow(T, n - k + 1)
v = f[::-1] # v(k-1) = (f(k-1), ..., f(0))
print(sum(R[0][j] * v[j] for j in range(k)) % MOD)Khi công thức có thêm “đồ phụ”. Đề thi hiếm khi cho truy hồi “sạch”. Bí quyết: đưa mọi thứ cần dùng vào vector trạng thái, kể cả hằng số 1, chỉ số $n$, hay tổng tiền tố. Miễn là mỗi thành phần ở bước sau đều là tổ hợp tuyến tính của các thành phần ở bước trước, ta dựng được ma trận. Bảng dưới là các dạng hay gặp nhất:
| Công thức | Vector trạng thái | Ma trận chuyển $T$ |
|---|---|---|
| $f(n) = f(n-1) + f(n-2) + d$ | $(f(n), f(n-1), 1)$ | $\begin{pmatrix}1 & 1 & d \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{pmatrix}$ |
| $f(n) = f(n-1) + n$ | $(f(n), n+1, 1)$ | $\begin{pmatrix}1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1\end{pmatrix}$ |
| Tổng $S(n) = F(1) + \ldots + F(n)$ (Fibonacci) | $(S(n), F(n+1), F(n))$ | $\begin{pmatrix}1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 0\end{pmatrix}$ |
| Hai dãy đan nhau: $a_n = a_{n-1} + 2b_{n-1}$, $b_n = a_{n-1} + b_{n-1}$ | $(a_n, b_n)$ | $\begin{pmatrix}1 & 2 \\ 1 & 1\end{pmatrix}$ |
| $f(n) = 4f(n-2) - f(n-4)$ (hệ số âm) | $(f(n), f(n-2))$, bước nhảy 2 | $\begin{pmatrix}4 & -1 \\ 1 & 0\end{pmatrix}$ với $-1 \equiv p - 1$ |
Bảng 2. Mỗi hàng của $T$ trả lời câu hỏi: “thành phần này ở bước sau bằng bao nhiêu lần mỗi thành phần ở bước trước?”. Ví dụ hàng 2 của dạng $f(n) = f(n-1) + n$: $(n+2) = 1 \cdot (n+1) + 1 \cdot 1$.
Thử kiểm tra dạng thứ hai với $f(0) = 0$: trạng thái đầu $v(0) = (0, 1, 1)$. Nhân $T$ được $(0 + 1, 1 + 1, 1) = (1, 2, 1)$, tức $f(1) = 1$; nhân tiếp được $(1 + 2, 3, 1)$, tức $f(2) = 3 = 0 + 1 + 2$. Đúng!
2. Với từng thành phần của $v(n+1)$, viết nó thành tổ hợp tuyến tính của các thành phần của $v(n)$. Hệ số chính là một hàng của $T$.
3. Xác định trạng thái đầu $v(n_0)$ đã biết, rồi $v(n) = T^{\,n - n_0} \cdot v(n_0)$. Xử lý riêng $n < n_0$.
4. Kiểm tra bằng tay 2–3 bước đầu (như đoạn trên) trước khi nộp. Rất nhiều bạn sai vì lệch số mũ 1 đơn vị.
Phần 5Đếm đường đi độ dài $k$ và QHĐ với $n$ lớn
Cho đồ thị có hướng $n$ đỉnh với ma trận kề $A$: $A[i][j]$ là số cạnh từ $i$ tới $j$. Hỏi có bao nhiêu đường đi độ dài đúng $k$ (đi qua đúng $k$ cạnh, được lặp lại đỉnh và cạnh) từ $u$ tới $v$?
Định lý: số đó bằng $(A^k)[u][v]$. Lý do rất tự nhiên: một đường đi độ dài $k$ từ $u$ tới $v$ = một đường đi độ dài $k-1$ từ $u$ tới đỉnh $w$ nào đó, rồi đi thêm cạnh cuối $w \to v$. Nên
$\text{cnt}_k[u][v] = \sum_{w} \text{cnt}_{k-1}[u][w] \cdot A[w][v]$,
và đây đúng là công thức nhân ma trận $\text{cnt}_k = \text{cnt}_{k-1} \cdot A$. Bắt đầu với $\text{cnt}_1 = A$ nên $\text{cnt}_k = A^k$. Em xem từng bước trong mô phỏng: mỗi lần nhân thêm $A$, ô $[u][v]$ được cộng từ những đỉnh $w$ có cạnh đi vào $v$:
Xem code C++ / Python: đếm đường đi độ dài k từ s tới t (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<long long>> Mat;
const long long MOD = 1000000007;
int n;
Mat mul(const Mat &A, const Mat &B){
Mat C(n, vector<long long>(n, 0));
for(int i = 0; i < n; i++)
for(int t = 0; t < n; t++){
if(A[i][t] == 0) continue;
for(int j = 0; j < n; j++)
C[i][j] = (C[i][j] + A[i][t] * B[t][j]) % MOD;
}
return C;
}
int main(){
int m, s, t;
long long k;
cin >> n >> m >> k >> s >> t;
Mat A(n, vector<long long>(n, 0));
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
A[u - 1][v - 1]++; // cạnh có hướng u -> v
}
Mat R(n, vector<long long>(n, 0));
for(int i = 0; i < n; i++) R[i][i] = 1;
while(k > 0){
if(k & 1) R = mul(R, A);
A = mul(A, A);
k >>= 1;
}
cout << R[s - 1][t - 1]; // (A^k)[s][t] = số đường đi độ dài k từ s tới t
return 0;
}import sys
MOD = 10**9 + 7
def mul(A, B):
cols = list(zip(*B))
return [[sum(x * y for x, y in zip(row, col)) % MOD for col in cols] for row in A]
data = sys.stdin.read().split()
n, m, k, s, t = map(int, data[:5])
A = [[0] * n for _ in range(n)]
for i in range(m):
u, v = int(data[5 + 2 * i]), int(data[6 + 2 * i])
A[u - 1][v - 1] += 1 # cạnh có hướng u -> v
R = [[int(i == j) for j in range(n)] for i in range(n)]
while k > 0:
if k & 1:
R = mul(R, A)
A = mul(A, A)
k >>= 1
print(R[s - 1][t - 1]) # (A^k)[s][t]Nối với quy hoạch động. Rất nhiều bài QHĐ đếm thực chất là đếm đường đi trên một đồ thị trạng thái nhỏ. Lấy ví dụ: đếm số xâu độ dài $n$ chỉ gồm chữ A, B, C mà không chứa “AB”. Khi thêm một chữ vào cuối, ta chỉ cần biết xâu hiện tại có tận cùng bằng A hay không:
- Trạng thái 0 (không tận cùng bằng A): thêm A sang trạng thái 1; thêm B hoặc C vẫn ở trạng thái 0.
- Trạng thái 1 (tận cùng bằng A): thêm A vẫn ở 1; thêm C về 0; thêm B thì tạo ra “AB”, cấm.
Hình 2. Đồ thị trạng thái của bài đếm xâu không chứa “AB”. Mỗi xâu hợp lệ độ dài $n$ là một đường đi độ dài $n$ xuất phát từ trạng thái 0 (xâu rỗng).
QHĐ thông thường: $dp[i][s]$ = số xâu độ dài $i$ kết thúc ở trạng thái $s$, và $dp[i][s'] = \sum_s dp[i-1][s] \cdot T[s][s']$, chạy $O(n)$. Nhưng công thức ấy chính là nhân vector hàng $dp[i-1]$ với ma trận $T$ cố định, nên $dp[n] = dp[0] \cdot T^n$ với $dp[0] = (1, 0)$. Đáp án là tổng hàng 0 của $T^n$.
| $i$ | $dp[i][0]$ | $dp[i][1]$ | Tổng | Kiểm tra |
|---|---|---|---|---|
| 0 | 1 | 0 | 1 | xâu rỗng |
| 1 | $1 \cdot 2 = 2$ | $1 \cdot 1 = 1$ | 3 | A, B, C |
| 2 | $2 \cdot 2 + 1 \cdot 1 = 5$ | $2 \cdot 1 + 1 \cdot 1 = 3$ | 8 | $3^2 - 1$ (bỏ “AB”) |
| 3 | $5 \cdot 2 + 3 = 13$ | $5 + 3 = 8$ | 21 | $27 - 6$ (bỏ ABx, xAB) |
Bảng 3. QHĐ đếm xâu không chứa “AB” trên ba bước đầu. Với $n = 10^{18}$, thay vòng lặp bằng $T^n$.
Xem code C++ / Python: đếm xâu A, B, C không chứa “AB” với n ≤ 10^18 (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
typedef array<array<ll, 2>, 2> M2;
M2 mul(const M2 &A, const M2 &B){
M2 C{};
for(int i = 0; i < 2; i++)
for(int t = 0; t < 2; t++)
for(int j = 0; j < 2; j++)
C[i][j] = (C[i][j] + A[i][t] * B[t][j]) % MOD;
return C;
}
int main(){
ll n;
cin >> n;
M2 T = {{{2, 1}, {1, 1}}}; // T[s][s'] = số chữ cái đưa trạng thái s sang s'
M2 R = {{{1, 0}, {0, 1}}};
while(n > 0){
if(n & 1) R = mul(R, T);
T = mul(T, T);
n >>= 1;
}
cout << (R[0][0] + R[0][1]) % MOD; // xuất phát ở trạng thái 0 (xâu rỗng), kết thúc ở đâu cũng được
return 0;
}MOD = 10**9 + 7
def mul(A, B):
return [[(A[i][0] * B[0][j] + A[i][1] * B[1][j]) % MOD for j in range(2)] for i in range(2)]
n = int(input())
T = [[2, 1], [1, 1]] # T[s][s'] = số chữ cái đưa trạng thái s sang s'
R = [[1, 0], [0, 1]]
while n > 0:
if n & 1:
R = mul(R, T)
T = mul(T, T)
n >>= 1
print((R[0][0] + R[0][1]) % MOD) # xuất phát ở trạng thái 0 (xâu rỗng)Cùng một cách nghĩ, em giải được hàng loạt bài QHĐ quen thuộc với $n$ khổng lồ: leo cầu thang mỗi bước 1, 2 hoặc 3 bậc (bài tập 3), xâu nhị phân không có ba số 1 liên tiếp (bài tập 4), lát nền $2 \times n$ hay $3 \times n$ bằng gạch $1 \times 2$ (bài tập 7), xâu không chứa một mẫu bất kỳ (bài tập 8, trạng thái là độ dài phần đang khớp với mẫu, giống ý tưởng của KMP ở bài 28).
i, t, j và bỏ qua A[i][t] == 0 như code mẫu giúp nhanh hơn đáng kể với ma trận thưa.- Cầu Thang Nhà A Phủ (DPSTEPS) (Dễ)
- Tìm xn (Trung bình)
- Lát Gạch (Trung bình)
- Concatenation of Consecutive Binary Numbers (LeetCode 1680) (Trung bình)
- Xâu Fibonacci (FIB2) (Khá)
Bài tậpLuyện lũy thừa ma trận
Dãy $G$ có $G(0) = a$, $G(1) = b$ và $G(n) = G(n-1) + G(n-2)$ với $n \ge 2$. Cho $a, b, n, m$ ($0 \le a, b \le 10^9$, $0 \le n \le 10^{18}$, $1 \le m \le 10^9 + 7$), hãy tính $G(n) \bmod m$.
2 1 10 1000000007123📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
1 % m.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll MOD;
struct M2 { ll a, b, c, d; };
M2 mul(M2 x, M2 y){
return { (x.a * y.a + x.b * y.c) % MOD, (x.a * y.b + x.b * y.d) % MOD,
(x.c * y.a + x.d * y.c) % MOD, (x.c * y.b + x.d * y.d) % MOD };
}
int main(){
ll a, b, n;
cin >> a >> b >> n >> MOD;
M2 res = {1 % MOD, 0, 0, 1 % MOD}, M = {1 % MOD, 1 % MOD, 1 % MOD, 0};
while(n > 0){
if(n & 1) res = mul(res, M);
M = mul(M, M);
n >>= 1;
}
// (G(n+1), G(n)) = M^n . (G(1), G(0)) = M^n . (b, a)
cout << (res.c * (b % MOD) + res.d * (a % MOD)) % MOD;
return 0;
}a, b, n, MOD = map(int, input().split())
def mul(x, y):
p, q, r, s = x
e, f, g, h = y
return ((p * e + q * g) % MOD, (p * f + q * h) % MOD, (r * e + s * g) % MOD, (r * f + s * h) % MOD)
res, M = (1 % MOD, 0, 0, 1 % MOD), (1 % MOD, 1 % MOD, 1 % MOD, 0)
while n > 0:
if n & 1:
res = mul(res, M)
M = mul(M, M)
n >>= 1
print((res[2] * b + res[3] * a) % MOD) # G(n) = hàng 1 của M^n nhân (b, a)Cho $n$ ($0 \le n \le 10^{18}$). Tính $S(n) = F(1) + F(2) + \ldots + F(n)$ theo modulo $10^9 + 7$, với $F(1) = F(2) = 1$.
512📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<long long>> Mat;
const long long MOD = 1000000007;
Mat mul(const Mat &A, const Mat &B){
int k = A.size();
Mat C(k, vector<long long>(k, 0));
for(int i = 0; i < k; i++)
for(int t = 0; t < k; t++){
if(A[i][t] == 0) continue;
for(int j = 0; j < k; j++)
C[i][j] = (C[i][j] + A[i][t] * B[t][j]) % MOD;
}
return C;
}
Mat matPow(Mat M, long long e){
int k = M.size();
Mat R(k, vector<long long>(k, 0));
for(int i = 0; i < k; i++) R[i][i] = 1;
while(e > 0){
if(e & 1) R = mul(R, M);
M = mul(M, M);
e >>= 1;
}
return R;
}
int main(){
long long n;
cin >> n;
// trạng thái (S(n), F(n+1), F(n)); S(n+1) = S(n) + F(n+1), F(n+2) = F(n+1) + F(n)
Mat T = {{1, 1, 0},
{0, 1, 1},
{0, 1, 0}};
Mat R = matPow(T, n);
// v(0) = (S(0), F(1), F(0)) = (0, 1, 0) nên S(n) = R[0][1]
cout << R[0][1];
return 0;
}import sys
MOD = 10**9 + 7
def mul(A, B):
cols = list(zip(*B))
return [[sum(x * y for x, y in zip(row, col)) % MOD for col in cols] for row in A]
def mat_pow(M, e):
k = len(M)
R = [[int(i == j) for j in range(k)] for i in range(k)]
while e > 0:
if e & 1:
R = mul(R, M)
M = mul(M, M)
e >>= 1
return R
n = int(input())
# trạng thái (S(n), F(n+1), F(n))
T = [[1, 1, 0],
[0, 1, 1],
[0, 1, 0]]
print(mat_pow(T, n)[0][1]) # v(0) = (0, 1, 0)Một cầu thang có $n$ bậc ($0 \le n \le 10^{18}$). Mỗi bước em leo được 1, 2 hoặc 3 bậc. Có bao nhiêu cách leo từ chân lên đúng bậc thứ $n$? In theo modulo $10^9 + 7$. (Với $n = 0$ có đúng 1 cách: đứng yên.)
47📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<long long>> Mat;
const long long MOD = 1000000007;
Mat mul(const Mat &A, const Mat &B){
int k = A.size();
Mat C(k, vector<long long>(k, 0));
for(int i = 0; i < k; i++)
for(int t = 0; t < k; t++){
if(A[i][t] == 0) continue;
for(int j = 0; j < k; j++)
C[i][j] = (C[i][j] + A[i][t] * B[t][j]) % MOD;
}
return C;
}
Mat matPow(Mat M, long long e){
int k = M.size();
Mat R(k, vector<long long>(k, 0));
for(int i = 0; i < k; i++) R[i][i] = 1;
while(e > 0){
if(e & 1) R = mul(R, M);
M = mul(M, M);
e >>= 1;
}
return R;
}
int main(){
long long n;
cin >> n;
long long f[3] = {1, 1, 2}; // f(0), f(1), f(2)
if(n < 3){ cout << f[n]; return 0; }
Mat T = {{1, 1, 1}, // f(i+1) = f(i) + f(i-1) + f(i-2)
{1, 0, 0},
{0, 1, 0}};
Mat R = matPow(T, n - 2); // v(n) = T^(n-2) . v(2), v(2) = (2, 1, 1)
cout << (R[0][0] * 2 + R[0][1] + R[0][2]) % MOD;
return 0;
}import sys
MOD = 10**9 + 7
def mul(A, B):
cols = list(zip(*B))
return [[sum(x * y for x, y in zip(row, col)) % MOD for col in cols] for row in A]
def mat_pow(M, e):
k = len(M)
R = [[int(i == j) for j in range(k)] for i in range(k)]
while e > 0:
if e & 1:
R = mul(R, M)
M = mul(M, M)
e >>= 1
return R
n = int(input())
f = [1, 1, 2]
if n < 3:
print(f[n])
else:
T = [[1, 1, 1], [1, 0, 0], [0, 1, 0]]
R = mat_pow(T, n - 2) # v(2) = (2, 1, 1)
print((R[0][0] * 2 + R[0][1] + R[0][2]) % MOD)Đếm số xâu nhị phân độ dài $n$ ($1 \le n \le 10^{18}$) không chứa ba chữ số 1 đứng liền nhau. In theo modulo $10^9 + 7$.
37📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<long long>> Mat;
const long long MOD = 1000000007;
Mat mul(const Mat &A, const Mat &B){
int k = A.size();
Mat C(k, vector<long long>(k, 0));
for(int i = 0; i < k; i++)
for(int t = 0; t < k; t++){
if(A[i][t] == 0) continue;
for(int j = 0; j < k; j++)
C[i][j] = (C[i][j] + A[i][t] * B[t][j]) % MOD;
}
return C;
}
Mat matPow(Mat M, long long e){
int k = M.size();
Mat R(k, vector<long long>(k, 0));
for(int i = 0; i < k; i++) R[i][i] = 1;
while(e > 0){
if(e & 1) R = mul(R, M);
M = mul(M, M);
e >>= 1;
}
return R;
}
int main(){
long long n;
cin >> n;
// trạng thái s = số chữ 1 liên tiếp ở cuối xâu (0, 1, 2)
Mat T = {{1, 1, 0}, // từ 0: thêm '0' -> 0, thêm '1' -> 1
{1, 0, 1}, // từ 1: thêm '0' -> 0, thêm '1' -> 2
{1, 0, 0}}; // từ 2: chỉ được thêm '0' -> 0
Mat R = matPow(T, n);
cout << (R[0][0] + R[0][1] + R[0][2]) % MOD; // bắt đầu từ xâu rỗng (trạng thái 0)
return 0;
}import sys
MOD = 10**9 + 7
def mul(A, B):
cols = list(zip(*B))
return [[sum(x * y for x, y in zip(row, col)) % MOD for col in cols] for row in A]
def mat_pow(M, e):
k = len(M)
R = [[int(i == j) for j in range(k)] for i in range(k)]
while e > 0:
if e & 1:
R = mul(R, M)
M = mul(M, M)
e >>= 1
return R
n = int(input())
T = [[1, 1, 0], # T[s][s'] = số cách thêm 1 ký tự đưa s sang s'
[1, 0, 1],
[1, 0, 0]]
print(sum(mat_pow(T, n)[0]) % MOD)Dãy $f$ cho bởi $f(0)$, $f(1)$ và $f(n) = a \cdot f(n-1) + b \cdot f(n-2) + n$ với $n \ge 2$. Cho $a, b, f(0), f(1)$ ($0 \le$ mỗi số $\le 10^9$) và $n$ ($0 \le n \le 10^{18}$), tính $f(n) \bmod (10^9 + 7)$.
1 1 0 1 526📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<long long>> Mat;
const long long MOD = 1000000007;
Mat mul(const Mat &A, const Mat &B){
int k = A.size();
Mat C(k, vector<long long>(k, 0));
for(int i = 0; i < k; i++)
for(int t = 0; t < k; t++){
if(A[i][t] == 0) continue;
for(int j = 0; j < k; j++)
C[i][j] = (C[i][j] + A[i][t] * B[t][j]) % MOD;
}
return C;
}
Mat matPow(Mat M, long long e){
int k = M.size();
Mat R(k, vector<long long>(k, 0));
for(int i = 0; i < k; i++) R[i][i] = 1;
while(e > 0){
if(e & 1) R = mul(R, M);
M = mul(M, M);
e >>= 1;
}
return R;
}
int main(){
long long a, b, f0, f1, n;
cin >> a >> b >> f0 >> f1 >> n;
if(n == 0){ cout << f0 % MOD; return 0; }
// trạng thái (f(i), f(i-1), i+1, 1)
Mat T = {{a % MOD, b % MOD, 1, 0}, // f(i+1) = a f(i) + b f(i-1) + (i+1)
{1, 0, 0, 0}, // f(i)
{0, 0, 1, 1}, // (i+2) = (i+1) + 1
{0, 0, 0, 1}}; // 1 giữ nguyên
Mat R = matPow(T, n - 1); // v(n) = T^(n-1) . v(1)
long long v[4] = {f1 % MOD, f0 % MOD, 2, 1};
long long ans = 0;
for(int j = 0; j < 4; j++) ans = (ans + R[0][j] * v[j]) % MOD;
cout << ans;
return 0;
}import sys
MOD = 10**9 + 7
def mul(A, B):
cols = list(zip(*B))
return [[sum(x * y for x, y in zip(row, col)) % MOD for col in cols] for row in A]
def mat_pow(M, e):
k = len(M)
R = [[int(i == j) for j in range(k)] for i in range(k)]
while e > 0:
if e & 1:
R = mul(R, M)
M = mul(M, M)
e >>= 1
return R
a, b, f0, f1, n = map(int, input().split())
if n == 0:
print(f0 % MOD)
else:
T = [[a % MOD, b % MOD, 1, 0], # trạng thái (f(i), f(i-1), i+1, 1)
[1, 0, 0, 0],
[0, 0, 1, 1],
[0, 0, 0, 1]]
R = mat_pow(T, n - 1)
v = [f1 % MOD, f0 % MOD, 2, 1]
print(sum(R[0][j] * v[j] for j in range(4)) % MOD)Cho đồ thị có hướng $n$ đỉnh ($2 \le n \le 30$), $m$ cạnh ($m \le n^2$, không có hai cạnh trùng nhau, có thể có khuyên) và số $k$ ($1 \le k \le 10^{18}$). Đếm số đường đi từ đỉnh 1 tới đỉnh $n$ có độ dài từ 1 tới $k$ (được lặp đỉnh, lặp cạnh). In theo modulo $10^9 + 7$. Dòng đầu là $n, m, k$, $m$ dòng sau mỗi dòng một cạnh $u \; v$.
3 4 4
1 2
2 3
3 1
1 35📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<long long>> Mat;
const long long MOD = 1000000007;
Mat mul(const Mat &A, const Mat &B){
int k = A.size();
Mat C(k, vector<long long>(k, 0));
for(int i = 0; i < k; i++)
for(int t = 0; t < k; t++){
if(A[i][t] == 0) continue;
for(int j = 0; j < k; j++)
C[i][j] = (C[i][j] + A[i][t] * B[t][j]) % MOD;
}
return C;
}
Mat matPow(Mat M, long long e){
int k = M.size();
Mat R(k, vector<long long>(k, 0));
for(int i = 0; i < k; i++) R[i][i] = 1;
while(e > 0){
if(e & 1) R = mul(R, M);
M = mul(M, M);
e >>= 1;
}
return R;
}
int main(){
int n, m;
long long k;
cin >> n >> m >> k;
Mat A(n + 1, vector<long long>(n + 1, 0)); // đỉnh 0..n-1 là đỉnh thật, đỉnh n là "hố"
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
A[u - 1][v - 1]++;
}
A[n - 1][n] = 1; // từ đích rơi vào hố
A[n][n] = 1; // hố tự lặp: đứng chờ cho đủ k + 1 bước
Mat R = matPow(A, k + 1);
cout << R[0][n];
return 0;
}import sys
MOD = 10**9 + 7
def mul(A, B):
cols = list(zip(*B))
return [[sum(x * y for x, y in zip(row, col)) % MOD for col in cols] for row in A]
def mat_pow(M, e):
k = len(M)
R = [[int(i == j) for j in range(k)] for i in range(k)]
while e > 0:
if e & 1:
R = mul(R, M)
M = mul(M, M)
e >>= 1
return R
data = sys.stdin.read().split()
n, m, k = int(data[0]), int(data[1]), int(data[2])
A = [[0] * (n + 1) for _ in range(n + 1)] # đỉnh n (đánh số từ 0) là "hố"
for i in range(m):
u, v = int(data[3 + 2 * i]), int(data[4 + 2 * i])
A[u - 1][v - 1] += 1
A[n - 1][n] = 1 # từ đích rơi vào hố
A[n][n] = 1 # hố tự lặp
print(mat_pow(A, k + 1)[0][n])Có bao nhiêu cách lát kín một nền hình chữ nhật $3 \times n$ ($0 \le n \le 10^{18}$) bằng các viên gạch $1 \times 2$ (được xoay dọc hoặc ngang)? In theo modulo $10^9 + 7$.
411📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
% trong C++ cho ra số âm.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<long long>> Mat;
const long long MOD = 1000000007;
Mat mul(const Mat &A, const Mat &B){
int k = A.size();
Mat C(k, vector<long long>(k, 0));
for(int i = 0; i < k; i++)
for(int t = 0; t < k; t++){
if(A[i][t] == 0) continue;
for(int j = 0; j < k; j++)
C[i][j] = (C[i][j] + A[i][t] * B[t][j]) % MOD;
}
return C;
}
Mat matPow(Mat M, long long e){
int k = M.size();
Mat R(k, vector<long long>(k, 0));
for(int i = 0; i < k; i++) R[i][i] = 1;
while(e > 0){
if(e & 1) R = mul(R, M);
M = mul(M, M);
e >>= 1;
}
return R;
}
int main(){
long long n;
cin >> n;
if(n % 2 == 1){ cout << 0; return 0; }
long long m = n / 2; // g(m) = 4 g(m-1) - g(m-2), g(0) = 1, g(1) = 3
if(m == 0){ cout << 1; return 0; }
Mat T = {{4, MOD - 1}, // -1 viết thành MOD - 1
{1, 0}};
Mat R = matPow(T, m - 1); // v(m) = T^(m-1) . (g(1), g(0)) = T^(m-1) . (3, 1)
cout << (R[0][0] * 3 + R[0][1]) % MOD;
return 0;
}import sys
MOD = 10**9 + 7
def mul(A, B):
cols = list(zip(*B))
return [[sum(x * y for x, y in zip(row, col)) % MOD for col in cols] for row in A]
def mat_pow(M, e):
k = len(M)
R = [[int(i == j) for j in range(k)] for i in range(k)]
while e > 0:
if e & 1:
R = mul(R, M)
M = mul(M, M)
e >>= 1
return R
n = int(input())
if n % 2 == 1:
print(0)
elif n == 0:
print(1)
else:
T = [[4, MOD - 1], [1, 0]] # g(m) = 4 g(m-1) - g(m-2)
R = mat_pow(T, n // 2 - 1)
print((R[0][0] * 3 + R[0][1]) % MOD) # (g(1), g(0)) = (3, 1)Xét các xâu độ dài $n$ ($1 \le n \le 10^{18}$) chỉ gồm $\sigma$ chữ cái thường đầu tiên của bảng chữ cái ($1 \le \sigma \le 26$). Cho xâu mẫu $P$ ($1 \le |P| \le 10$, chỉ gồm các chữ cái đó). Đếm số xâu không chứa $P$ như một đoạn con liên tiếp, theo modulo $10^9 + 7$. Dữ liệu: dòng 1 là $n$ và $\sigma$, dòng 2 là $P$.
3 3
ab21📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<long long>> Mat;
const long long MOD = 1000000007;
Mat mul(const Mat &A, const Mat &B){
int k = A.size();
Mat C(k, vector<long long>(k, 0));
for(int i = 0; i < k; i++)
for(int t = 0; t < k; t++){
if(A[i][t] == 0) continue;
for(int j = 0; j < k; j++)
C[i][j] = (C[i][j] + A[i][t] * B[t][j]) % MOD;
}
return C;
}
Mat matPow(Mat M, long long e){
int k = M.size();
Mat R(k, vector<long long>(k, 0));
for(int i = 0; i < k; i++) R[i][i] = 1;
while(e > 0){
if(e & 1) R = mul(R, M);
M = mul(M, M);
e >>= 1;
}
return R;
}
int main(){
long long n;
int sigma;
string P;
cin >> n >> sigma >> P;
int L = P.size();
// trạng thái j = độ dài tiền tố dài nhất của P đang khớp ở cuối xâu (0..L-1)
Mat T(L, vector<long long>(L, 0));
for(int j = 0; j < L; j++)
for(int c = 0; c < sigma; c++){
string s = P.substr(0, j) + char('a' + c);
int nj = min((int)s.size(), L);
while(nj > 0 && s.substr(s.size() - nj) != P.substr(0, nj)) nj--; // L <= 10 nên thử hết
if(nj < L) T[j][nj]++; // nj == L: vừa xuất hiện P, bỏ
}
Mat R = matPow(T, n);
long long ans = 0;
for(int j = 0; j < L; j++) ans = (ans + R[0][j]) % MOD;
cout << ans;
return 0;
}import sys
MOD = 10**9 + 7
def mul(A, B):
cols = list(zip(*B))
return [[sum(x * y for x, y in zip(row, col)) % MOD for col in cols] for row in A]
def mat_pow(M, e):
k = len(M)
R = [[int(i == j) for j in range(k)] for i in range(k)]
while e > 0:
if e & 1:
R = mul(R, M)
M = mul(M, M)
e >>= 1
return R
data = sys.stdin.read().split()
n, sigma, P = int(data[0]), int(data[1]), data[2]
L = len(P)
T = [[0] * L for _ in range(L)]
for j in range(L): # j = độ dài tiền tố của P đang khớp ở cuối
for c in range(sigma):
s = P[:j] + chr(97 + c)
nj = min(len(s), L)
while nj > 0 and s[len(s) - nj:] != P[:nj]:
nj -= 1
if nj < L: # nj == L: vừa xuất hiện P, bỏ
T[j][nj] += 1
print(sum(mat_pow(T, n)[0]) % MOD)
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét