神题
胡乱讲述一下思维过程
首先, 读懂题.
然后, 转化问题为构造一个长度为 | T|+n 的字符串, 使其内含有 T 这个子序列.
之后, 想到一个简单的 dp. 由于是回文串, 我们就增量构造半个回文串, 设 f(i,j,k) 为构造到第 i 个位置, 从前往后匹配到 j, 从后往前匹配到 k, 这样 O(m*m*n)(没有观察到其转移的性质会再乘个 26).
再然后, 发现不妙, 在最后讨论奇偶.
(我的思路到此为止)
接着, 观察其转移的实质, 发现其实 dp 的过程就是在一个有限状态自动机上行走, 而有限状态自动机上的状态就是目前剩下的 T, 所以我们只不过是要求出从起点到某些点的路径条数 (事先声明步数).
到了现在, 我们的目的只不过是统计到不同终点的路径条数, 那么: 第一步, 点集相同的路径合并起来, 点集不同, 一定不同; 第二步, 对于点集相同的路径们, 他们走自环的总数一定, 分配不同, 一定不同; 第三步, 对于点集相同且分配相同的路径们, 他们每次走自环, 走得不同, 一定不同. 接着观察, 对于自环数一定的状态, 是一样的, 而且只有 3 种, 并且他们的顺序也没有关系了 (可以从组合数的角度看出), 至此, 对于每一种状态数量都相同且点集相同的路径, 我们都可以合并, 并且还可以算出合并之后的路径类在不计算内部影响下的贡献和.
好了, 现在该怎么处理上面最后合并出来的每一种路径的内部贡献呢? 直接在原自动机上搞, 肯定不行, 每一种处理一次好一些, 但是还是过不了, 我们考虑建立一个大图, 利用邻接矩阵的次幂的性质, 我们就可以直接 get 到每两个点之间的距离, 我们只要保证在这个大图上能 get 到所有我们想要的信息就可以了, 所以现在我们把之前的自动机合并成一个大自动机就 ok 了.
最后, 把前两步的信息合并, 就好了.
好牛逼的有限状态自动机啊, 感觉就像一个两端匹配的 AC 自动机, 而且匹配的还是子序列.
还有这个组合数学也是牛的一笔, 甚至还利用组合意义合并路径.
而且那个转大图建立邻接矩阵也是超 66666666666666666
(似乎还有组合数做法看不懂)
(把 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;
- }
来源: http://www.bubuko.com/infodetail-2507222.html