BZOJ 1009 GT考试 DP+矩阵快速幂

本文主要是介绍BZOJ 1009 GT考试 DP+矩阵快速幂，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

dp[i][j]表示长度为i，匹配了j个的方案数，压缩成矩阵，转移即可。

#include <cstdio>
#include <cstring>
using namespace std;
struct Mat
{
int a[22][22];
};
Mat I, A;
int n, m, mod;
char s[22], ss[22];
Mat mul(Mat& x, Mat& y)
{
Mat z;
memset(z.a, 0, sizeof(z.a));
for(int i = 0; i < m; i++)
{
for(int j = 0; j < m; j++)
{
for(int k = 0; k < m; k++)
{
z.a[i][j] += x.a[i][k]*y.a[k][j];
z.a[i][j] %= mod;
}
}
}
return z;
}
void pow_mod(int x)
{
while(x)
{
if(x&1)
{
I = mul(I, A);
}
A = mul(A, A);
x >>= 1;
}
}
int main()
{
scanf("%d %d %d", &n, &m, &mod);
scanf("%s", s+1);
int l = strlen(s+1);
strcpy(ss+1, s+1);
for(int i = l-1; i >= 0; i--)
{
char c = ss[i+1];
for(int j = 0; j <= 9; j++)
{
s[i+1] = c;
if(j == s[i+1]-'0')
{
A.a[i+1][i]++;
continue;
}
s[i+1] = j+'0';
for(int k = i; k >= 0; k--)
{
if(k == 0)
{
A.a[k][i]++;
continue;
}
int t = i+1;
int k2;
for(k2 = k; k2 >= 1; k2--, t--)
{
if(s[k2] != s[t])
break;
}
if(k2 == 0)
{
A.a[k][i]++;
//printf("***%d %d\n", k, j);
//printf("%s", s+1);
break;
}
}
}
}   
/*for(int i = 0; i < m; i++)
{
for(int j = 0; j < m; j++)
printf("%d ", A.a[i][j]);
puts("");
}*/
memset(I.a, 0, sizeof(I.a));
for(int i = 0; i < m; i++)
I.a[i][i] = 1;
pow_mod(n);
int ans = 0;
for(int i = 0; i < m; i++)
{
ans += I.a[i][0];
ans %= mod;
}
printf("%d\n", ans);
return 0;
}

这篇关于BZOJ 1009 GT考试 DP+矩阵快速幂的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---