HDU 5459 Jesus Is Here（递推）

http://acm.hdu.edu.cn/showproblem.php?pid=5459

题意：

S(1) = c，S(2) = ff， S(3) = cff，之后S(i) = S(i-1)+S(i-2)。

现在给出n，求S(n)中任意两个c之间距离的总和。

思路：
现在假设第i-1和第i-2要合成第i个，计算S(i)的过程如下：

ans[i] = ans[i-1]+ans[i-2]+add，现在要求就是add新增的部分值。

假设S(i-2)中有2个c，下标分别为{a，b}（下标以1为起始点计）总长度为len2，S(i-1)中有3个c，下标为别为{x，y，z}，总长度为len1。

那么新增的部分就是(len2-a)+x+ (len2-a)+y + (len2-a)+z +(len2-b)+x +(len2-b)+y +(len2-b)+z，也就是(len2-a+len2-b)*3 + (x+y+z)*2。

这里的话(len2-a+len2-b)就是S(i-2)中所有c点到末端的距离之和，3是S(i-1)中c的个数，x+y+z是S(i-1)中所有c点到始端的距离之和，2是S(i-2)中c的个数。

所有维护四个值进行递推，len是长度，sum是所有c点到末端的距离之和（到始端的距离之和可以通过len和sum计算出来），num是c的个数，ans是最终答案。

 #include<iostream>

 #include<cstdio>

 using namespace std;

 const int mod = ;

 const int maxn = +;

 long long len[maxn],num[maxn],sum[maxn],ans[maxn];

 void init()

 {

     len[] = , num[] = , sum[] = , ans[] = ;

     len[] = , num[] = , sum[] = , ans[] = ;

     len[] = , num[] = , sum[] = , ans[] = ;

     len[] = , num[] = , sum[] = , ans[] = ;

     for(int i=;i<=;i++)

     {

         len[i] = (len[i-]+len[i-])%mod;

         num[i] = (num[i-]+num[i-])%mod;

         ans[i] = (ans[i-]+ans[i-]+sum[i-]*num[i-]+(((len[i-]*num[i-]-sum[i-])%mod)*num[i-])%mod)%mod;

         sum[i] = ((sum[i-]+sum[i-])%mod+(num[i-]*len[i-])%mod)%mod;

     }

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     int T;

     int kase = ;

     init();

     scanf("%d",&T);

     while(T--)

     {

         int n;

         scanf("%d",&n);

         printf("Case #%d: %lld\n",++kase,ans[n]);

     }

     return ;

 }