【BZOJ1009】GT考试

  设f[i][j]表示共i位数字,其后缀与不吉利数字最多匹配j位的方案数，则f[i]与f[i-1]的关系可以预处理出来，然后矩阵快速幂。

  由于懒预处理就直接暴力了。

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=22;

void readchar(char &ch) {while ((ch=getchar())=='\n' || ch==' ');}

int n,m,k;
int a[maxn];

struct Matrix
{
	int a[maxn][maxn];
	int row,col;
	void Init() {memset(a,0,sizeof(a));}

	friend Matrix operator* (const Matrix &a,const Matrix &b);
}ans,pre,_v;

Matrix operator* (const Matrix &a,const Matrix &b)
{
	_v.Init();
	_v.row=a.row;_v.col=b.col;
	for (int i=0;i<a.row;i++)
	for (int j=0;j<b.col;j++)
	for (int l=0;l<a.col;l++)
	_v.a[i][j]=(_v.a[i][j]+a.a[i][l]*b.a[l][j])%k;
	return _v;
}

void Init()
{
	scanf("%d%d%d",&n,&m,&k);
	char ch;
	for (int i=1;i<=m;i++) readchar(ch),a[i]=ch-'0';
	for (int i=0;i<m;i++) for (int j=0;j<=9;j++) for (int l=i+1;l>=0;l--) if (l==0 || a[l]==j)
	{
		int flag=1;
		for (int t=1;t<l;t++) if (a[i-l+1+t]!=a[t]) flag=0;
		pre.a[i][l]+=flag;
		if (flag) break;
	}
	pre.row=pre.col=m;
	ans.row=1;ans.col=m;
	ans.a[0][0]=1;
}

void DP()
{
	while (n)
	{
		if (n&1) ans=ans*pre;
		n>>=1;
		pre=pre*pre;
	}
	int res=0;
	for (int i=0;i<m;i++) res=(res+ans.a[0][i])%k;
	printf("%d\n",res);
}

int main()
{
	Init();
	DP();
	return 0;
}