HDU 5136 Yue Fei's Battle

题目链接：HDU-5136
网上的一篇题解非常好，所以就直接转载了。转自oilover的博客
代码：
 1 #include<cstring>
 2 #include<cstdio>
 3 #include<queue>
 4 using namespace std;
 5 typedef long long LL;
 6 const LL MAXN=100000;
 7 const LL MOD=1000000007;
 8 
 9 LL dp[MAXN+10],sum[MAXN+10];
10 LL mod2,mod6;
11 LL extgcd(LL a,LL b,LL &x,LL &y)
12 {
13     LL d=a;
14     if(b!=0)
15     {
16         d=extgcd(b,a%b,y,x);
17         y-=(a/b)*x;
18     }
19     else { x=1; y=0; }
20     return d;
21 }
22 LL modInverse(LL a,LL m)
23 {
24     LL x,y;
25     extgcd(a,m,x,y);
26     return (m+x%m)%m;
27 }
28 void init()
29 {
30     mod2=modInverse(2,MOD);
31     mod6=modInverse(6,MOD);
32     memset(dp,0,sizeof(dp));
33     memset(sum,0,sizeof(sum));
34     dp[0]=dp[1]=1;
35     sum[0]=1;
36     sum[1]=2;
37     for(LL i=2;i<=MAXN;i++)
38     {
39         dp[i]=(dp[i-1]*sum[i-2] % MOD + dp[i-1]*(dp[i-1]+1) %MOD *mod2 % MOD)%MOD;
40         sum[i]=(sum[i-1]+dp[i])%MOD;
41     }
42 }
43 LL f(LL kk)
44 {
45     LL k=kk/2;
46     if(kk%2==0)
47         return dp[k]*(dp[k]+1)%MOD *mod2 % MOD;
48     LL ans=0;
49     ans =(ans + dp[k]*(dp[k]+1)%MOD *mod2 %MOD *sum[k-1] %MOD) %MOD;
50     ans =(ans + dp[k]) %MOD;
51     ans =(ans + dp[k]*((dp[k]-1+MOD)%MOD) %MOD) %MOD;
52     if(dp[k]>=3) ans =(ans + dp[k]*(dp[k]-1)%MOD*(dp[k]-2)%MOD*mod6%MOD)%MOD;
53     return ans;
54 }
55 int main()
56 {
57 #ifdef LOCAL
58     freopen("in.txt","r",stdin);
59     // freopen("out.txt","w",stdout);
60 #endif
61     init();
62     LL k;
63     while(scanf("%lld",&k)!=EOF && k)
64         printf("%lld
",f(k));
65     return 0;
66 }