Problem DescriptionI’ve sent Fang Fang around 201314 text messages in almost 5 years. Why can’t she make sense of what I mean?
“But Jesus is here!” the priest intoned. “Show me your messages.”
Fine, the first message is s1=‘‘c” and the second one is s2=‘‘ff”.
The i-th message is si=si−2+si−1 afterwards. Let me give you some examples.
s3=‘‘cff”, s4=‘‘ffcff” and s5=‘‘cffffcff”.
“I found the i-th message’s utterly charming,” Jesus said.
“Look at the fifth message”. s5=‘‘cffffcff” and two ‘‘cff” appear in it.
The distance between the first ‘‘cff” and the second one we said, is 5.
“You are right, my friend,” Jesus said. “Love is patient, love is kind.
It does not envy, it does not boast, it is not proud. It does not dishonor others, it is not self-seeking, it is not easily angered, it keeps no record of wrongs.
Love does not delight in evil but rejoices with the truth.
It always protects, always trusts, always hopes, always perseveres.”
Listen – look at him in the eye. I will find you, and count the sum of distance between each two different ‘‘cff” as substrings of the message. InputAn integer T (1≤T≤100), indicating there are T test cases.
Following T lines, each line contain an integer n (3≤n≤201314), as the identifier of message. OutputThe output contains exactly T lines.
Each line contains an integer equaling to:
∑i<j:sn[i..i+2]=sn[j..j+2]=‘‘cff”(j−i) mod 530600414,
where sn as a string corresponding to the n-th message. Sample Input9
5
6
7
8
113
1205
199312
199401
201314 Sample OutputCase #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 Source2015 ACM/ICPC Asia Regional Shenyang Online Recommendwange2014 | We have carefully selected several similar problems for you: 6343 6342 6341 6340 6339
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 201314
#define mod 530600414
#define gep(i,a,b) for(int i=a;i<=b;i++)
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
int t,id;
ll f[N+],c[N+],s[N+],n[N+];
/*
f ； 任意两个c的坐标差之和
c : 字符串里c的个数
s : 字符串里所有的c的坐标和
n ； 字符串的长度
例如 ：
cffffcff ffcffcffffcff
((8-6)+(8-1))*3
3*2+6*2+11*2
上面两个式子的和==f[7]
(1+6)+(3+6+11)+8*3==s[7]
*/ void init()
{
c[]=,s[]=,n[]=,f[]=;
c[]=,s[]=,n[]=,f[]=;
gep(i,,N){
f[i]=( (f[i-]+f[i-])%mod + (((c[i-]*n[i-]-s[i-])%mod+mod)%mod)*c[i-]%mod +(c[i-]*s[i-]%mod) )%mod;
c[i]=(c[i-]+c[i-])%mod;
n[i]=(n[i-]+n[i-])%mod;
s[i]=((s[i-]+s[i-])%mod+(c[i-]*n[i-])%mod)%mod;
//if(i<=12)printf("%lld %lld %lld %lld\n",f[i],c[i],n[i],s[i]);
}
}
int main()
{
init();
scanf("%d",&t);
gep(i,,t){
scanf("%d",&id);
printf("Case #%d: %lld\n",i,f[id]);
}
return ;
}
