题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5459
题目描述：给定一个递推得来的字符串，问字符串中不同cff之间的距离之和，
递推规则：
s1=c; s2=ff
sn=s[n-2]s[n-1];
可以观察到任意一个c都被两个ff包含，所以相当于求任意两个c之间的距离之和。
设s[n-2]为p1,p2,p3,,,,p[x],s[n-1]为q1,q2,q3,,,,q[y];
X和y分别为字符串中c的个数；设cnt_c[i]为第i个字符串中c的个数,
all[i]表示第i个字符串的长度，
那么合并之后字符串为p1,p2,p3,,,,p[cnt_c[i-2]],q1+all[i-2],q2+all[i-2],q3+all[i-2]+,,,,q[cnt_c[i-1]]+all[i-2]
设T[i]表示第i个字符串中任意两个c的距离和，
T[i]=T[i-1]+T[i-2]+F[i];
现在讨论F[i]，首先考虑q1与之前的组合，
q1+all[i-2]-p1,q1+all[i-2]-p2,q1+all[i-2]-p3,,,q1+all[i-2]-p[cnt_c[i-2]];
合并之后就为：( q1+all[i-2] )*cnt_c[i-2] - (p1+p2+p3,,,+p[cnt_c[i-2]]);
加上q2,q3,,,q[cnt_c[i-1]]之后，答案就为(q1+q2+q3+,,,q[cnt_c[i-1]])*cnt_c[i-2]
+ all[i-2]*cnt_c[i-2] *cnt_c[i-1] - (p1+p2+p3,,,+p[cnt_c[i-2]])*cnt_c[i-1];
设s[i]表示第i个字符串中不同c之间的距离之和，
T[i]=T[i-2] + T[i-1] + s[i-1]*cnt_c[i-2] + all[i-2]*cnt_c[i-2] *cnt_c[i-1] - s[i-2]*cnt_c[i-1];
如果答案是负数,第一可能是(a%MOD+MOD)%MOD,第二可能是long long写成int了
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cstring>
#include <iostream>
#define mod 530600414
#define MOD 530600414
#define maxn 201315
#define LL long long
using namespace std;
LL s[maxn],cnt_c[maxn],all[maxn],T[maxn];
//cnt_c代表字符串中有多少个c
//all代表字符串中有多少个字符
//s代表字符串中c位置的和
//T[i]=(cnt_c[i-2]*s[i-1] + cnt_c[i-1] * cnt_c[i-2] *all[i-2] -cnt_c[i-1]*s[i-2]);
void solve()
{
// memset(T,0,sizeof(T));
cnt_c[]=; cnt_c[]=;
all[]=; all[]=;
s[]=; s[]=;
T[]=; T[]=;
for(int i=;i<=;i++)
{
cnt_c[i]=(cnt_c[i-]+cnt_c[i-])%MOD;
all[i]=(all[i-]+all[i-])%MOD;
s[i]=( (s[i-]+s[i-])%MOD + (cnt_c[i-]*all[i-]) %MOD ) %MOD; int a1=( ( ((cnt_c[i-]*all[i-])%MOD - (s[i-] ) ) %MOD *cnt_c[i-])%MOD )%MOD;
int b1=(cnt_c[i-] * s[i-] ) %MOD;
T[i]=((T[i-]+ T[i-]%MOD +MOD)) %MOD;
T[i]=( (T[i]+a1+b1)%MOD +MOD)%MOD;
}
}
int main()
{
// freopen("test.txt","r",stdin);
int t,Case=;
scanf("%d",&t);
solve();
while(t--)
{
int input;
scanf("%d",&input);
printf("Case #%d: %lld\n",++Case,T[input]);
}
return ;
}