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


/*
    題意：?jiǎn)栭L(zhǎng)度為n的bad serial串的個(gè)數(shù)。bad serial 指每一個(gè)長(zhǎng)度為m的子串都不是good serial
    (good serial指要么全相同，要么全不同)，所以bad serial就是兩個(gè)以上不同，但不能m個(gè)都不同

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

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


    心得：只考慮最后一個(gè)字符（第i+1），考慮怎么合法過來的
           dp轉(zhuǎn)移時(shí)，由之前的轉(zhuǎn)移過來難寫的話，寫成從當(dāng)前擴(kuò)展到之后的！
           按照題意定義狀態(tài)，這里要2個(gè)以上不同，定義末尾有j個(gè)不同（j=1時(shí)是特殊情況，即末尾可以幾個(gè)連續(xù)相同）
*/
#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自動(dòng)機(jī)，然后DP打表的.....