這道題我是email一下maxwell_blueing，還有請教了watashi神牛才會做的。非常感謝這兩位


/*
    題意：問長度為n的bad serial串的個數。bad serial 指每一個長度為m的子串都不是good serial
    (good serial指要么全相同，要么全不同)，所以bad serial就是兩個以上不同，但不能m個都不同

    dp[i,j](1<=j<m)表示長度為i的串最后j個數字互不相同的串個數（即str[i-j]與末尾這j個數中一個相同）

    考慮dp[i+1,j+1]
    (1)dp[i+1,j+1]+=dp[i,j]*(m-j)   選一個與i及之前j個數字都不同的
    (2)dp[i+1,k]+=dp[i,j]  2<=k<=j  選一個與i之前j個數字某個相同的 str[i+1]=str[i+1-k]
    還有一種特殊的就是dp[i,1]，即末尾幾個數字都相同的合法串個數
    (3)dp[i+k,1]+=dp[i,j]  (1+k<=m-1, j>1||i==1)
    如果j=1的話有可能一連串都相同導致不合法，要j>1
    特殊的是i=1，j=1就可取，因為1之前沒有數字，認為與1不同（跟j>1一樣）


    心得：只考慮最后一個字符（第i+1），考慮怎么合法過來的
           dp轉移時，由之前的轉移過來難寫的話，寫成從當前擴展到之后的！
           按照題意定義狀態，這里要2個以上不同，定義末尾有j個不同（j=1時是特殊情況，即末尾可以幾個連續相同）
*/
#include<cstdio>
#include<algorithm>

const int MOD = 987654321;

long long dp[110][10];

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m),n>0)
    {
        if(m==1){puts("0");continue;}
        if(m==2){printf("%d\n",n==1?2:0);continue;}

        memset(dp,0,sizeof(dp));
        dp[1][1]=m;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<m;j++)
            {
                dp[i][j]%=MOD;

                dp[i+1][j+1]+=dp[i][j]*(m-j);//str[i+1]=new one
                for(int k=2;k<=j;k++)
                    dp[i+1][k]+=dp[i][j];//str[i+1]=str[i+1-k]

                if(j>1||i==1)
                {
                    for(int k=1;1+k<=m-1;k++)
                    {
                        dp[i+k][1]+=dp[i][j];
                    }
                }
            }
        }

        long long ans=0;
        for(int j=1;j<m;j++)
        {
            ans+=dp[n][j];
        }
        printf("%I64d\n",ans%MOD);
    }
    return 0;
}



起初想不出，然后是建立AC自動機，然后DP打表的.....