[HNOI2008] GT考试 思路 状态转移矩阵T[i][j]其实就是添加一个字符之后从状态i转移到状态j的方案数量，也就是先用kmp得到对应的T然后对于长度为N的串只需要让这个转移矩阵N次方就行了，然后Tn[0][j]就是子串最大匹配到j位的方案数，所求结果就是Tn[0][0]一直加到Tn[0][M-1](M是子串的长度)。 算法 KMP 自动机建模 + 矩阵快速幂 主要函数以及主要流程 矩阵相乘函数 矩阵快速幂函数(利用到矩阵相乘函数和快速幂算法) kmp算法(过于基础就不介绍了) 利用next函数得到基础转移矩阵T[m][n] 对T运用幂n函数得到Tn Tn按照思路直接操作就行了 题解（借鉴了AI，自己敲的，我太强了） #include<bits/stdc++.h> using namespace std; typedef long long ll; // 得到next函数 vector<int> getNext(string pattern) { int m = pattern.size(); vector<int> next(m,0); for(int i=1,j=0;i<m;i++) { while(j!=0 && pattern[i] != pattern[j]) j = next[j-1]; if(pattern[j] == pattern[i]) j++; next[i] = j; } return next; } // 矩阵相乘函数 vector<vector<int>> matMul(vector<vector<int>> a,vector<vector<int>> b,int K) { int m = a.size(); vector<vector<int>> res(m,vector<int>(m,0)); //结果 for(int i=0;i<m;i++) // i-k,k-j { for(int k=0;k<m;k++) { if(a[i][k]!=0) //剪枝减小工作量 { for(int j=0;j<m;j++) { res[i][j] = (res[i][j] + (ll)a[i][k] * b[k][j]) % K; } } } } return res; } // 矩阵幂函数(利用快速幂算法) vector<vector<int>> matPow(vector<vector<int>> a,int p,int K) { int m = a.size(); vector<vector<int>> res(m,vector<int>(m,0)); //结果 for(int i=0;i<m;i++) res[i][i] = 1; //单位矩阵用于起步 while(p!=0) { if(p & 1) res = matMul(res,a,K); a = matMul(a,a,K); p >>= 1; // p /= 2 } return res; } int main() { int N,M,K; // M<=20 N<=1e9 K<=10000,所以不能暴力解 cin >> N >> M >> K; string pattern; // 子串（此题中指的是不该出现的子串） cin >> pattern; // 求 pattern 的状态转移方程T[i][j] // 因为要用到pattern的next数组，所以先求next vector<int> next = getNext(pattern); vector<vector<int>> T(M,vector<int>(M,0)); // T[M][M],表示基础转移矩阵 for(int m=0;m<M;m++) // m为当前匹配数量,由于不准出现匹配到完整M的，所以最大长度为M-1 { for(int digit=0;digit<=9;digit++) // 尝试每一个数字,从而进行状态转移 { int cur = m; // 从当前位置开始回退 while(cur!=0 && (pattern[cur]-'0') != digit) cur = next[cur-1]; if((pattern[cur]-'0') == digit) cur++; if(cur < M) T[m][cur] = (T[m][cur] + 1) % K; } } // 得到完整的状态转移矩阵 vector<vector<int>> Tn = matPow(T,N,K); ll result = 0; for(int i=0;i<M;i++) { result = (result + Tn[0][i]) % K; } cout << result << endl; return 0; } 遇到问题 p>>1不会改变p的值应该是p>>=1 int类型乘法要注意防止溢出，一般用ll

（加图改md路径）改了

生活大爆炸版石头剪刀布 思路 数字化选择方式 纯手抄一个map<pair<int, int>, int> mp用来记录出拳结果。如mp[{2,0}] = 2;表示b赢了 直接取余数组处理得到结果 题解 #include <bits/stdc++.h> using namespace std; int main() { // 0 表示 剪刀， // 1 表示 石头， // 2 表示 布， // 3 表示 蜥蜴人， // 4 表示 斯波克 // 结果0表示平局，1表示a赢，2表示b赢 map<pair<int, int>, int> mp; int n,na,nb; int result[3]={0}; //0无意义，1为a分数，2为b分数 cin >> n >> na >> nb; vector<int> a(na),b(nb); for (int i=0;i<na;i++) { cin >> a[i]; } for (int i=0;i<nb;i++) { cin >> b[i]; } for(int i=0;i<5;i++) { mp[{i,i}] = 0; } mp[{2,0}] = 2; mp[{3,0}] = 2; mp[{3,1}] = 2; mp[{4,2}] = 2; mp[{4,3}] = 2; mp[{1,0}] = 1; mp[{2,1}] = 1; mp[{3,2}] = 1; mp[{4,0}] = 1; mp[{4,1}] = 1; mp[{0,2}] = 1; mp[{0,3}] = 1; mp[{1,3}] = 1; mp[{2,4}] = 1; mp[{3,4}] = 1; mp[{0,1}] = 2; mp[{1,2}] = 2; mp[{2,3}] = 2; mp[{0,4}] = 2; mp[{1,4}] = 2; for(int i=0;i<n;i++) { int xi = i%na; int x = a[i%na]; int y = b[i%nb]; result[mp[{x,y}]]++; } cout << result[1] << " " << result[2] << endl; return 0; } 优化 看了别人的题解，大多是用一个二维[5][5]的数组存储对局输赢，后面处理简单一些。