MYF

HDU 5642 King's Order

Posted on | In | | Visitors

题目链接

HDU 5642

题目分析

题目大意

BestCoder #75c 中文题面

解析

第一次做数位DP的，长知识了，核心代码看注释。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define eps 1e-8
#define INF 0x3f3f3f3f
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
#define maxn 100000+5
#define mod 1000000007
ll dp[2005][4];
ll ans[2005]={1};
int main(){
    for (int i=1; i<=2000; i++) {
        //第i位与i-1位不同，共有dp[i][0]种方法
        dp[i][0]=25*ans[i-1]%mod;
        if (i==1)
            dp[i][0]++;
        ans[i]+=dp[i][0];
        
        //j=1时: 第i位与第i-1位相同
        //j=2时: 第j位与第i-1,i-2位相同
        for (int j=1; j<3; j++) {
            dp[i][j]=dp[i-1][j-1];
            ans[i]+=dp[i][j];
            ans[i]%=mod;
        }
    }
    
    int t;
    cin>>t;
    while (t--) {
        int k;
        cin>>k;
        cout<<ans[k]<<endl;
    }
}