[CF 506E] Mr. Kitayuta's Gift

作法：

關於這題的官方解，前面寫的還蠻清楚的，不過後面有跳過一些東西，所以這裡只把後半部的詳細解釋一下。對了，我習慣用$n$代表字串長度，而題目裡的多加字母的個數則用$m$表示。從官方解中的第一張大圖開始（有$O(n^2)$個紅綠節點的那張圖），因為每條鍊是獨立的，所以我們可以分開計算每條鍊上的答案再加起來。而單看一條鍊時，現在上面有一些紅綠交錯的節點，這時可以發現其實他們排列的順序其實不影響答案，只和他是幾個紅點幾個綠點組成的有關，所以可以任意交換位置，才能變成官方解圖中「先全部都是紅再全部都是綠」的鍊。因此這時候我們得到了很多種很類似的鍊，並且我們知道每種鍊的倍率，也就是每種鍊分別有幾條（或是說當我們算完每條鍊的答案之後他們分別要乘以多少，加起來才是答案）。假設第$i$種鍊有$i$個紅點，那麼可以推出此時有$\left \lceil \frac{n-i}{2} \right \rceil$個綠點，如下圖。（這裡舉$n=6$當例子）

在圖中黑色代表紅點，白色則是綠點，並且圖中沒有畫出自己轉移到自己的邊，還有所有最右邊的點都連到終點。所以接下來的問題是怎麼把這些鍊縮成一條鍊，讓我們可以用一次矩陣快速冪就求出答案。我們用一個座標$(x,y)$來代表一種鍊，指的是這條鍊有$x$個黑點和$y$個白點，那麼有個重要的性質就是：$(x,y)$其實可以拆成$(x+1,y)$和$(x+1,y-1)$，因為如果考慮這條鍊中的第一個白點，把「他轉移到他自己的第$25$條邊」轉移到的點改成另一個白點，這個白點的環境跟原本的白點一樣，那麼原本的白點就變成黑點了（只有24條自己轉移到自己的邊），如下圖。

並且也不難證明這兩張圖從起點走到終點的路徑可以一一對應。而這樣子改掉之後從起點走到兩個終點的路徑就不相干了，因此可以把他們拆開來，也就是一條$(3,2)$的方法數會等於一條$(4,1)$的方法數$+$一條$(4,2)$的方法數。我們把所有的$(x,y)$畫到座標平面上來看，並且在對應的點寫上這種鍊有幾條，那麼剛剛「分裂」的過程就可以表示成下面這張圖：

其中每個黑點上都有一個權值，代表這種鍊有幾條，並且當$(x,y)$分裂的時候就是把$(x+1,y)$的權值還有$(x+1,y-1)$的權值都加上$(x,y)$的權值。因此我們可以把所有點都分裂成圖中紅色的點，或是更一般來說把所有鍊都變成$(\left \lceil \frac{n}{2} \right \rceil,0),(\left \lceil \frac{n}{2} \right \rceil+1,0),...,(n,0),(n,1),...,(n,\left \lceil \frac{n}{2} \right \rceil)$的樣子，並且我們也知道此時每種鍊分別有幾條。此時這些鍊就可以很輕鬆的合併成下面這個自動機了！（其中藍色的點是終點）

更一般的，共有$n$個黑點，$\left \lceil \frac{n}{2} \right \rceil$個白點，並且從第$\left \lceil \frac{n}{2} \right \rceil$個黑點一直到最後一個點都有連向終點的邊。而這邊注意到還得考慮「每種鍊的倍率」的問題，而解決方法不難，例如$(3,0)$這種鍊有$a$條，那麼就把第三個黑點轉移到終點的方法數設為$a$，其他以此類推。這樣就可以直接求起點到終點有幾條所求長度的路徑就可以了（對了，要記得這些點都有自己轉移到自己的邊）。

最後還有詳解最後一部份的「扣掉違反規則的字串個數」，先回去看第一張官方解的大圖，看那些代表$dp[i][i+1]$的節點們，如果有綠色的節點，那麼就代表從起點走到這個節點的長度為$K-1$的路徑都是不滿足條件的。於是我們可以把「代表$dp[i][i+1]$的綠節點們」當成終點，所以這時候也可以把所有的路徑都拆開，並且一樣用DP求出「有$x$個黑點的路徑」分別有幾條，再作一次上述的步驟就可以了。而這兩次不一樣的地方在於：如果這次有$x$個黑點，那麼白點的個數會是$\left \lceil \frac{n-2-i}{2} \right \rceil$，還有這次從終點到終點的轉移只有$25$種，第一次作的時候是有$26$種的。

code :

#include<bits/stdc++.h>
#define MOD 10007
using namespace std;
const int maxn=200+2 ;
 
int pow(int x,int n)
{
    if(n<=1) return n ? x : 1 ;
    int tmp=pow(x,n/2) ;
    if(n%2) return (tmp*tmp%MOD)*x%MOD ;
    else return tmp*tmp%MOD ;
}
 
struct mat
{
    int n,m,a[maxn*3/2][maxn*3/2] ;
    mat(int _n,int _m){n=_n , m=_m ; memset(a,0,sizeof(a)) ;}
};
 
mat mul(const mat &p,const mat &q)
{
    mat r(p.n,q.m) ;
    for(int i=0;i<p.n;i++) for(int j=0;j<q.m;j++)
        for(int k=0;k<p.m;k++)
        r.a[i][j]+=p.a[i][k]*q.a[k][j] ,
        r.a[i][j]%=MOD ;
    return r ;
}
 
int getnum(mat &p,int st,int ed,int K)
{
    mat q(p.n,1) ; q.a[st][0]=1 ;
    for(;K;K>>=1,p=mul(p,p)) if(K&1) q=mul(p,q) ;
    return q.a[ed][0] ;
}
 
int t[maxn][maxn] ;
int solve(int *d,int n,int K,int type)
{/// coordinate : ( x , ceil((n-x)/2) ) => (red number , green number)
    memset(t,0,sizeof(t)) ;
    int ha=(n+1)/2 ;
    for(int i=0;i<=n;i++) t[i][(n-i+1)/2]=d[i] ;
    for(int i=0;i<n;i++) for(int j=1;j<=ha;j++)
        t[i+1][j]=(t[i+1][j]+t[i][j])%MOD ,
        t[i+1][j-1]=(t[i+1][j-1]+t[i][j])%MOD ,
        t[i][j]=0 ;
 
    int GOAL=0 ;
    mat p(n+ha+1,n+ha+1) ;
    for(int i=2;i<=n+ha;i++) p.a[i][i-1]=1 ;
    for(int i=1;i<=n+ha;i++) p.a[i][i]=(i<=n ? 24 : 25) ;
    for(int i=ha;i<=n+ha;i++) p.a[GOAL][i]=(i<=n ? t[i][0] : t[n][i-n]) ;
    p.a[GOAL][GOAL]=(type==1 ? 26 : 25) ;
    return getnum(p,1,0,K) ;
}
 
char s[maxn] ;
int dp[maxn][maxn][maxn] ;
void DP(int n,int type)
{
    memset(dp,0,sizeof(dp)) ;
    for(int i=n;i>=1;i--) for(int j=i;j<=n;j++)
    {
        if(type==1)
        {
            if(i==j){dp[i][j][0]=1 ; continue ;}
        }
        else
        {
            if(i==j) continue ;
            if(j==i+1){dp[i][j][0]=(s[i]==s[j]?1:0) ; continue ;}
        }
        if(s[i]==s[j])
        {
            for(int k=0;k<=n;k++)
                dp[i][j][k]=dp[i+1][j-1][k] ;
            if(j==i+1) dp[i][j][0]=1 ;
        }
        else
        {
            dp[i][j][0]=0 ;
            for(int k=1;k<=n;k++)
                dp[i][j][k]=(dp[i+1][j][k-1]+dp[i][j-1][k-1])%MOD ;
        }
    }
}
 
main()
{
    int n,m ; scanf("%s%d",s+1,&m) ;
    n=strlen(s+1) ;
 
    DP(n,1) ;
 
    int K=(n+m+1)/2 ;
    int ans=solve(dp[1][n],n,K,1) ;
    if(n==1 || (n+m)%2==0){printf("%d\n",ans) ; return 0 ;}
    if(n==2 && s[1]==s[2])
        ans=(ans-pow(25,K-1)+MOD)%MOD ;
    else if(n!=2)
    {
        DP(n,2) ;
        ans=(ans-solve(dp[1][n],n-2,K-1,2)+MOD)%MOD ;
    }
    printf("%d\n",ans) ;
}