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 ;
}