首页 > 代码库 > 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考试
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。