首页 > 代码库 > BZOJ 1009 GT考试

BZOJ 1009 GT考试

首先,f[i][j]表示准考证后i个和不吉利数字前j个匹配种类数。

于是f[i][j]=Σf[i-1][k]*g[k][j],其中g为匹配k个到匹配j个的方案数。(暴力预处理)

然后矩阵快速幂即可,注意不能从匹配m个状态转出来。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int n,m,k,p[25],top=0;char s[25];struct matrix{    int a[25][25];}a,b;int ask(){    for (int i=top;i>=1;i--)    {        int p1=1,p2=top-i+1;        while ((s[p1]-0==p[p2]) && (p2<=top)) p1++,p2++;        if (p2==top+1) return i;    }    return 0;}void get_table(){    for (int i=0;i<=m;i++)        for (int j=0;j<=m;j++)            a.a[i][j]=b.a[i][j]=0;    a.a[0][0]=1;b.a[0][1]=1;b.a[0][0]=9;    for (int i=1;i<=m-1;i++)    {        p[++top]=s[i]-0;        for (int j=0;j<=9;j++)        {            p[++top]=j;            b.a[i][ask()]=(b.a[i][ask()]+1)%k;            p[top--]=0;        }    }}matrix mul(matrix a,matrix b){    matrix c;    for (int i=0;i<=m;i++)        for (int j=0;j<=m;j++)            c.a[i][j]=0;    for (int i=0;i<=m;i++)        for (int j=0;j<=m;j++)            for (int kk=0;kk<=m;kk++)                c.a[i][j]=(c.a[i][j]+(a.a[i][kk]*b.a[kk][j])%k)%k;    return c;}void f_pow(int y){    while (y)    {        if (y&1) a=mul(a,b);        b=mul(b,b);        y>>=1;    }}int main(){    scanf("%d%d%d",&n,&m,&k);    scanf("%s",s+1);    get_table();    f_pow(n);    int sum=0;    for (int i=0;i<=m-1;i++)        sum=(sum+a.a[0][i])%k;    printf("%d\n",sum);    return 0;}

 

BZOJ 1009 GT考试