Sample Input
9
5
6
7
8
113
1205
199312
199401
201314
Sample Output
Case #1: 5
Case #2: 16
Case #3: 88
Case #4: 352
Case #5: 318505405
Case #6: 391786781
Case #7: 133875314
Case #8: 83347132
Case #9: 16520782
题目要求当前字符串序列中某项里cff前缀两两间差值的和。
假设已经纪录了cff前缀的位置，
当前第k个字符串的位置为
v[1], v[2], …v[cnt(k)]
其中cnt(k)表示当前字符串cff前缀的个数。
那么对于k+1
u[1], u[2], …u[cnt(k+1)]
然后组合两个串
v[1], v[2], …v[cnt(k)], u[1]+len(k), u[2]+len(k),…, u[cnt(k+1)]+len(k)
其中len(k)表示第k个字符串的长度。
考虑前半部分v的内部差的和为sum(k), 后半部分u的内部和为sum(k+1)
然后就差交叉部分。
考虑v[i]，
自然是u[1]+len(k)-v[i] + u[2]+len(k)-v[i] +…+ u[cnt(k+1)]+len(k)-v[i]
化简得s[k+1]+cnt(k+1)*len(k)-cnt(k+1)*v[i]
然后对i求和
cnt(k)*s[k+1]+cnt(k)*cnt(k+1)*len(k)-cnt(k+1)*s[k]
于是sum就是上面三部分的和。
然后只需要同时维护s, cnt, len即可。
s[k+2]=s[k]+s[k+1]+cnt(k+1)*len(k)
cnt(k+2)=cnt(k+1)+cnt(k)
len(k+2)=len(k+1)+len(k)
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <string>
#define LL long long
#define MOD 530600414 using namespace std; const int maxN = ;
int n;
LL cnt[maxN], s[maxN], len[maxN], sum[maxN]; void init()
{
cnt[] = cnt[] = ;
s[] = ; s[] = ;
len[] = ; len[] = ;
sum[] = sum[] = ;
for (int i = ; i < maxN; ++i)
{
cnt[i] = (cnt[i-]+cnt[i-])%MOD;
s[i] = (s[i-]+s[i-]+cnt[i-]*len[i-]%MOD)%MOD;
len[i] = (len[i-]+len[i-])%MOD;
sum[i] = (sum[i-]+sum[i-])%MOD;
sum[i] += (cnt[i-]*s[i-]%MOD+(cnt[i-]*cnt[i-]%MOD)*len[i-]%MOD-cnt[i-]*s[i-]%MOD)%MOD;
sum[i] = (sum[i]%MOD+MOD)%MOD;
}
} int main()
{
//freopen("test.in", "r", stdin);
init();
int T;
scanf("%d", &T);
for (int times = ; times < T; ++times)
{
scanf("%d", &n);
printf("Case #%d: %d\n", times+, sum[n]);
}
return ;
}