HDU 5642 King's Order【デジタルdp】

テーマリンク:
http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=677&pid=1003
件名:
長さnのシーケンスを求めて、各文字(a~z)は連続して3回を超えない種類が現れます.
分析:
デジタルdpは、dp[i][j]を設定してi番目の文字に進行し、現在の文字がj回出て、状態が変わるごとに移動すればいいです.
コード:

#include <cstdio>
const int maxm = 2005, mod = 1e9+7;
long long dp[maxm][4];
int main (void)
{
    int T;scanf("%d",&T);
    dp[0][1] = 26;
    for(int i = 1; i < 2005; i++){
        dp[i][2] = dp[i - 1][1]%mod;
        dp[i][3] = dp[i - 1][2]%mod;
        dp[i][1] = (dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]) %mod * 25;
    }
    while(T--){
        int n;
        scanf("%d",&n);
        printf("%d
",(dp[n - 1][1] + dp[n - 1][2] + dp[n - 1][3])%mod);
    }
}