%d under git space getch pla scan n-2 矩阵乘法
题目大意:
准考证号为N位数X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数
他的不吉利数A1A2...Am(0<=Ai<=9)有M位,不出现是指X1X2...Xn中没有恰好一段等于A1A2...Am
A1和X1可以为0
思路:
dp i j 为第i个号码匹配到第j个不吉利数字的方案数
可以得到:dp[i][j]=∑dp[i?1][k]?t[k][j](0<=k<=m?1)
其中t数组为第i位加的字符的方案数使从匹配k位到匹配j位的方案数
可以使用kmp算法来求出t数组
然后这个式子可以矩阵乘法加速
同样在图上填一填数
- #include < iostream > #include < cstdio > #include < algorithm > #include < cmath > #include < cstdlib > #include < cstring > #include < queue > #include < map > #include < vector > #define ll long long#define inf 2147483611#define MAXN 1010 using namespace std;
- inline int read() {
- int x = 0,
- f = 1;
- char ch = getchar();
- while (!isdigit(ch)) {
- if (ch == ‘ - ‘) f = -1;
- ch = getchar();
- }
- while (isdigit(ch)) {
- x = x * 10 + ch - ‘0‘;
- ch = getchar();
- }
- return x * f;
- }
- int n,
- m,
- MOD,
- nxt[25];
- char str[25];
- struct mat {
- int num[25][25];
- }
- ans,
- t;
- mat mul(mat a, mat b) {
- mat res;
- memset(res.num, 0, sizeof(res.num));
- for (int i = 0; i < m; i++) for (int j = 0; j < m; j++) for (int k = 0; k < m; k++)(res.num[i][j] += a.num[i][k] * b.num[k][j]) %= MOD;
- return res;
- }
- int q_pow(int n) {
- int res = 0;
- while (n) {
- if (n & 1) ans = mul(ans, t);
- t = mul(t, t);
- n >>= 1;
- }
- for (int i = 0; i < m; i++)(res += ans.num[0][i]) %= MOD;
- return res;
- }
- int main() {
- n = read(),
- m = read(),
- MOD = read();
- scanf("%s", str + 1);
- int j = 0,
- tmp;
- for (int i = 2; i <= m; i++) {
- while (j && str[j + 1] != str[i]) j = nxt[j];
- if (str[j + 1] == str[i]) j++;
- nxt[i] = j;
- //cout<<i<<" "<<nxt[i]<<endl;
- }
- memset(t.num, 0, sizeof(t.num));
- memset(ans.num, 0, sizeof(ans.num));
- for (int i = 0; i < m; i++) for (int j = 0; j <= 9; j++) {
- tmp = i;
- while (tmp && str[tmp + 1] != (char)(j + ‘0‘)) tmp = nxt[tmp];
- if (str[tmp + 1] == (char)(j + ‘0‘)) tmp++;
- if (tmp != m) t.num[i][tmp]++;
- //cout<<i<<" "<<tmp<<endl;
- }
- for (int i = 0; i < m; i++) ans.num[i][i] = 1;
- printf("%d", q_pow(n));
- }
bzoj 1009 GT考试
%d under git space getch pla scan n-2 矩阵乘法
原文:http://www.cnblogs.com/yyc-jack-0920/p/7943775.html
来源: http://www.bubuko.com/infodetail-2413846.html