算法训练 K好数

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 using namespace std;
 6 const int maxn=150;
 7 const int mod=1000000007;
 8 int dp[maxn][maxn];
 9 
10 int main()
11 {
12     int k,l;
13     while(~scanf("%d%d",&k,&l))
14     {
15         memset(dp,0,sizeof(dp));
16         int sum1,sum2;
17         sum1=k-1;
18         for(int j=1;j<k;j++)
19             dp[1][j]=1;
20         for(int i=2;i<=l;i++)
21         {
22             sum2=0;
23             dp[i][0]=(sum1-dp[i-1][1]+mod)%mod;
24             sum2=dp[i][0];
25             for(int j=1;j<k-1;j++)    
26             {
27                 dp[i][j]=(((sum1-dp[i-1][j-1]+mod)%mod)-dp[i-1][j+1]+mod)%mod;
28                 sum2=(sum2+dp[i][j])%mod;
29             }
30             dp[i][k-1]=(sum1-dp[i-1][k-2]+mod)%mod;
31             sum2=(sum2+dp[i][k-1])%mod;
32             sum1=sum2;
33         }    
34         printf("%d\n",sum1);
35         
36         
37 
38     }    
39     return 0;
40 }