(我的思路到此为止……)

(似乎还有组合数做法……看不懂……)
(把dp状态搞到有限状态自动机上似乎是套路???)

```#pragma GCC optimize("O3")
#include <cstdio>
#include <cstring>
#include <algorithm>
const int P=10007,N=201;
char s[N];
int n,m,f[N][N][2],dp[N][N][N],R,G,B,S,a[N<<1][N<<1],temp[N<<1][N<<1],b[N<<1][N<<1];
inline void DP(){
register int i,j,l,r;
dp[1][m][0]=1;
for(i=m;i>0;--i)
for(l=1,r=i;r<=m;++l,++r)
for(j=0;j<=(m-i);++j){
if(!dp[l][r][j])continue;
if(s[l]==s[r]){
if(l+1==r)
(dp[0][0][j]+=dp[l][r][j])%=P;
else if(l==r){
(dp[0][0][j]+=dp[l][r][j])%=P;
if(n&1)(f[j][(m-j+1)>>1][0]+=dp[l][r][j])%=P;
}else
(dp[l+1][r-1][j]+=dp[l][r][j])%=P;
}else{
(dp[l+1][r][j+1]+=dp[l][r][j])%=P;
(dp[l][r-1][j+1]+=dp[l][r][j])%=P;
}
}
for(i=0;i<=m;++i)
(f[i][(m-i+1)>>1][1]+=((n&1)?26:1)*dp[0][0][i])%=P;
}
#define red(a) (a)
#define green(a) (R+(a))
#define blue(a) (R+G+(a))
inline void Multi1(){
memset(temp,0,sizeof(temp));
register int i,j,k;
for(i=1;i<=S;++i)
for(j=1;j<=S;++j)
if(a[i][j])
for(k=1;k<=S;++k)
if(b[j][k])
(temp[i][k]+=a[i][j]*b[j][k])%=P;
memcpy(b,temp,sizeof(b));
}
inline void Multi2(){
memset(temp,0,sizeof(temp));
register int i,j,k;
for(i=1;i<=S;++i)
for(j=1;j<=S;++j)
if(a[i][j])
for(k=1;k<=S;++k)
if(a[j][k])
(temp[i][k]+=a[i][j]*a[j][k])%=P;
memcpy(a,temp,sizeof(a));
}
inline void MUL(){
int i;
R=m,G=(m+1)>>1,B=G,S=R+G+B;
for(i=1;i<=R;++i){
a[red(i)][red(i)]=24;
if(i!=1)a[red(i)][red(i-1)]=1;
else a[red(i)][green(1)]=1;
}
for(i=1;i<=G;++i){
a[green(i)][green(i)]=25;
a[green(i)][blue(i)]=1;
if(i!=G)a[green(i)][green(i+1)]=1;
}
for(i=1;i<=B;++i)
a[blue(i)][blue(i)]=26;
for(i=1;i<=S;++i)b[i][i]=1;
int mi=n>>1;
while(mi){
if(mi&1)Multi1();
Multi2(),mi>>=1;
}
}
inline void CAL(){
int ans=0,i,j;
for(i=0;i<=R;++i)
for(j=1;j<=B;++j)
if(f[i][j][1])
(ans+=f[i][j][1]*b[i==0?green(1):red(i)][blue(j)])%=P;
if(n&1)
for(i=0;i<=R;++i)
for(j=1;j<=G;++j)
if(f[i][j][0])
(ans+=f[i][j][0]*b[i==0?green(1):red(i)][green(j)])%=P;
printf("%d\n",ans);
}
int main(){
scanf("%s%d",s+1,&n);
m=strlen(s+1),n+=m;
DP(),MUL(),CAL();
return 0;
}```

(0)
(0)

0条