Mình thấy bài này dù được rate ngang với bài trước nhưng số AC và SUBMIT là giảm gấp 3 nên mình nghĩ cần có một người viết solution 😅
## KHUYÊN CÁC BẠN NÊN SUY NGHĨ TRƯỚC KHI ĐỌC SOLUTION NHAAA
## Ý tưởng
- Để có thể nhìn ra hướng nhân ma trận đầu tiên ta cần có công thức **quy hoạch động** "trâu". Ta có
thể nhanh chóng suy ra công thức **QHĐ** như sau:
- Gọi $f[i][c]$ là số từ hợp lệ có độ dài $i$ mà kết thúc bằng chữ $c$.
- $f[i][c]$ sẽ là tổng của mọi $f[i-1][c']$ trong đó $c'$ là những chữ cái mà $c$ được đứng sau.
- Kết quả của một truy vấn $n, c$ là $f[n][c]$
- Hướng QHĐ này sẽ cho chúng ta độ phức tạp $O(n * 26^2)$ mỗi truy vấn, **TLE**.
- Từ đây ta có thể tối ưu bằng cách nhân ma trận.
## Cách giải
- Ta tạo một ma trận 1D $M$ kích thước $26$ để chứa kết quả, trong đó $M[i]$ là số từ hợp lệ kết thúc bằng chữ $i$
- Bây giờ ta cần nghĩ ra một ma trận $A$ sao cho $M*A$ cho ta trạng thái tiếp theo
- Dựa trên cách tính tích vô hướng 2 ma trận (các bạn có thể đọc [lý thuyết nhân ma trận](https://en.wikipedia.org/wiki/Matrix_multiplication))
ta thấy $M[i] = \Sigma M[j]$ với mọi $A[i][j] = 1$
- Vậy $A[i][j] = 1$ khi ký tự $j$ được đứng sau ký tự $i$ **"GIÁC NGỘ"** đây chính là mảng input đề bài,
bất ngờ chưa :).
- Sau khi có mảng A, với mỗi truy vấn $n, c$
ta chỉ cần lũy thừa nó lên *(n - 1)* lần và nhân lại với mảng *M*. Kết quả chúng ta nằm ở M[c]
- *(optional)* **NHƯNG** do M chúng ta có trạng thái ban đầu $là M[0..25] = 1$ (1 từ độ dài 1 có thể kết thúc bằng bất kỳ ký tự nào)
cho nên chúng ta hoàn toàn co thể bỏ luôn mảng M, mà kết quả sẽ là tổng của mọi giá trị A[0..25][c].
## CODE
**[ARE YOU SURE YOU WANT TO PROCEED]**
```cpp
/*
3/9/2025
Author : KevinPhan
*/
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define upb upper_bound
#define lwb lower_bound
#define FILE(task) freopen(task".inp","r",stdin);freopen(task".out","w",stdout);
#define int ll
typedef long long ll;
typedef long double lldb;
///--------------------------------------------------------------------------------///
//VARIABLES
const int MOD = 1e9 + 7;
vector<vector<int>> inp(26, vector<int>(26, 0));
int n, q;
char c;
//FUNCTIONS
vector<vector<int>> multMatrix(vector<vector<int>> x, vector<vector<int>> y)
{
int row = x.size();
int col = y[0].size();
int rep = y.size();
vector<vector<int>> res(row, vector<int>(col, 0));
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
for (int k = 0; k < rep; k++)
{
res[i][j] = (res[i][j] + (x[i][k] * y[k][j] % MOD)) % MOD;
}
}
}
return res;
}
vector<vector<int>> powMatrix(vector<vector<int>> x, int y)
{
int tmp = x.size();
vector<vector<int>> res(tmp, vector<int>(tmp, 0));
for (int i = 0; i < tmp; i++) res[i][i] = 1;
while(y)
{
if (y & 1) res = multMatrix(res, x);
x = multMatrix(x, x);
y >>= 1;
}
return res;
}
//PROCESS
void read()
{
for (int i = 0; i < 26; i++) for (int j = 0; j < 26; j++)
{
cin >> inp[i][j];
}
cin >> q;
}
void solve()
{
while (q--)
{
cin >> n >> c;
vector<vector<int>> base = inp;
base = powMatrix(base, n - 1);
int res = 0;
for (int i = 0; i < 26; i++)
{
res = (res + base[i][c - 'a']) % MOD;
}
cout << res << '\n';
}
}
//MAIN
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
//FILE("test");
read();
solve();
return 0;
}
```
kevinPhan
Created at
3 likes