HDU 5459 Jesus Is Here

Problem Description

I'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.

Input

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.

Output

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

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<iostream>
using namespace std;
const int maxn=300005;
typedef long long LL;
const LL base=530600414;
int T,t=0,n;

struct point
{
    LL l,r,x,c,len;
    point(){};
    point(LL l,LL r,LL x,LL c,LL len):l(l),r(r),x(x),c(c),len(len){}; 
}f[maxn];

void init()
{
    f[1]=point(0,0,1,0,1);
    f[2]=point(0,0,0,0,2);
    f[3]=point(0,2,1,0,3);
    f[4]=point(2,2,1,0,5);
    for (int i=5;i<=201314;i++)
    {
        f[i].len=(f[i-1].len+f[i-2].len)%base;
        f[i].x=(f[i-1].x+f[i-2].x)%base;
        f[i].l=(f[i-2].l+f[i-1].l+f[i-1].x*f[i-2].len)%base;
        f[i].r=(f[i-1].r+f[i-2].r+f[i-2].x*f[i-1].len)%base;
        f[i].c=(f[i-1].c+f[i-2].c+f[i-1].x*f[i-2].r+f[i-2].x*f[i-1].l+f[i-1].x*f[i-2].x)%base;
    }
}

int main()
{
    init();
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d",&n);
        printf("Case #%d: %d\n",++t,f[n].c);
    }
    return 0;
}