为朋友做的网站,舆情处置的五个步骤,网剧推广一次5元,网页美工设计教程百度网盘1305. GT考试
题意#xff1a;
准考证长度为n位#xff0c;不吉利数字有m位#xff0c;问不出现不吉利数字的准考证有多少种#xff0c;答案mod K
题解#xff1a;
动态规划kmp矩阵快速幂 设dp[i][j]表示长度为i#xff0c;且不包含S串#xff0c;且末尾部分与S串的…1305. GT考试
题意
准考证长度为n位不吉利数字有m位问不出现不吉利数字的准考证有多少种答案mod K
题解
动态规划kmp矩阵快速幂 设dp[i][j]表示长度为i且不包含S串且末尾部分与S串的前缀匹配的最大长度是j的所有字符串的集合 S串为不吉利数字 现在相同部分为j再黄色串后面再添加一个新数有10种选择0~9 如果添加的正好等于红色对应部分那j 如果不等于就重新匹配最长部分该如何快速匹配用kmp的next数组knext[k]实现快速匹配最长长度 转移方程 dp[i1][k]dp[i][k] 我们现在考虑两层状态之间的关系即dp[i1][…]与dp[i][…]的关系,我们可以列出这个式子 dp[i1,0]a00 * dp[i,0] a01 * dp[i,1]… dp[i1,1]a10 * dp[i,0] a11 * dp[i,1]… 而这些a可以组成一个矩阵A 由此可以得到 dp[i1] dp[i] *A 所以dp[n] f[n-1] *A …F[0] * An F[0]表示长度为0的情况F[0] 1 A怎么得到我们已经说过 dp[i1][k]dp[i][k]也就是dp[i1] dp[i] *A所以我们就把dp[i][k]加到对应的小a上即可也就是动态规划里的状态我们加到A矩阵里然后A求n-1次幂矩阵快速幂
代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b)
typedef long long ll;
using namespace std;inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn35;
int n,m,mod;
char str[maxn];
int ne[maxn];
int a[maxn][maxn];
void mul(int c[][maxn],int a[][maxn],int b[][maxn])
{static int t[maxn][maxn];memset(t,0,sizeof(t));for(int i0;im;i){for(int j0;jm;j){for(int k0;km;k){t[i][j](t[i][j]a[i][k]*b[k][j])%mod;}}}memcpy(c,t,sizeof(t));
}
int qmi(int k)
{int f0[maxn][maxn]{1};while(k){if(k1)mul(f0,f0,a);//f0f0*amul(a,a,a);//aa*ak1;}int res0;for(int i0;im;i)res(resf0[0][i])%mod;return res;
}
int main()
{cinnmmod;cinstr1;for(int i2,j0;im;i){while(jstr[j1]!str[i])jne[j];if(str[j1]str[i])j;ne[i]j; }//初始化A矩阵 for(int j0;jm;j){for(int c0;c9;c){int kj;while(kstr[k1]!c)kne[k];if(str[k1]c)k;if(km)a[j][k];}}//F[n]F[0]*A^ncoutqmi(n)endl;return 0;
}
