【誤差推定】[HNOI 2008][HYSBZ/BZOJ 1011]遠い惑星
タイトルリンク
ぶんせき
数値が比較的に小さい暴力、比較的に大きい時、分母は平均値を取ります
コード#コード#
ぶんせき
数値が比較的に小さい暴力、比較的に大きい時、分母は平均値を取ります
コード#コード#
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAXM 20
int n,m,k,cir,ans;
struct matrix{
int a[MAXM+1][MAXM+1];
matrix(int n){
memset(a,0,sizeof a);
for(int i=0;i<n;i++)
a[i][i]=1;
}
matrix(){
memset(a,0,sizeof a);
}
matrix operator*(const matrix &b)const{
matrix c;
int i,j,l;
for(i=0;i<m;i++)
for(j=0;j<m;j++)
for(l=0;l<m;l++)
c.a[i][j]=(c.a[i][j]+a[i][l]*b.a[l][j])%k;
return c;
}
void operator*=(const matrix &b){
*this=*this*b;
}
}a;
char x[MAXM+10];
void Read(int &x){
char c;
while(c=getchar(),c!=EOF)
if(c>='0'&&c<='9'){
x=c-'0';
while(c=getchar(),c>='0'&&c<='9')
x=x*10+c-'0';
ungetc(c,stdin);
return;
}
}
void read(){
Read(n),Read(m),Read(k);
scanf("%s",x+1);
}
matrix quick_pow(matrix c,int b){
matrix ret(m),a(c);
while(b){
if(b&1)
ret*=a;
a*=a;
b>>=1;
}
return ret;
}
void solve(){
int i,j,l,y;
for(i=0;i<m;i++){
for(j='0';j<='9';j++){
for(l=i+1;l;l--){
if(x[l]==j){
for(y=0;y<l-1;y++)
if(x[l-y-1]!=x[i-y])
break;
if(y==l-1)
break;
}
}
a.a[i][l]++;
}
}
a=quick_pow(a,n);
for(i=0;i<m;i++)
ans=(ans+a.a[0][i])%k;
}
int main()
{
read();
solve();
printf("%d
",ans);
}