HDOJ 5459 Jesus Is Here(打表法則)

Jesus Is Here
Time Limit: 1500/1000 MS (Java/Others)    Memory Limit: 65535/102400 K (Java/Others) Total Submission(s): 405    Accepted Submission(s): 290
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
An 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.
 
Output
The output contains exactly
T lines.
Each line contains an integer equaling to:
∑iwhere
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



    
    
    
                ，        ，     ，         ，       ，  ， ..... ac  ：

    
    
    
    
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define MAXN 210000
#define MOD 530600414
using namespace std;
long long len[MAXN],pos[MAXN],sum[MAXN],num[MAXN];
void db()
{
    len[5]=8;len[6]=13;
    num[5]=2;num[6]=3;
    pos[5]=7;pos[6]=20;
    sum[5]=5;sum[6]=16;
    for(int i=7;i<MAXN;i++)
    {
        len[i]=(len[i-2]+len[i-1])%MOD;
        num[i]=(num[i-2]+num[i-1])%MOD;
        pos[i]=(pos[i-1]+pos[i-2]+(len[i-2]*num[i-1])%MOD)%MOD;
        sum[i]=(sum[i-1]+sum[i-2]+(((len[i-2]*num[i-2]-pos[i-2]))%MOD*num[i-1])%MOD+(pos[i-1]*num[i-2])%MOD)%MOD;
    }
}
int main()
{
    db();
    int t;
    int n;
    int cas=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        printf("Case #%d: %lld
",++cas,sum[n]);
    }
    return 0;
}