hdu 5459 Jesus Is Here（数学，斐波那契）

本文链接：https://blog.csdn.net/acm_cxq/article/details/51599241

Jesus Is Here

Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 65535/102400 K (Java/Others)
Total Submission(s): 511 Accepted Submission(s): 367

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:

\sum i < j : s n [i . . i + 2] = s n [j . . j + 2] = ‘ ‘ cff " (j - i) m o d 530600414,

where

sn as a string corresponding to the

n -th message.

Sample Input

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

题意：有一个串S，S[1]=c，S[2]=ff，之后S[n]=S[n-2]S[n-1] 问你第n个字符串中所有cff相互之间的距离之和

思路：首先可以明确所有cff相互之间的距离之和就是所有c相互之间的距离之和，因为c之后必跟着ff

那么问题就在于如何求出字符串中所有c之间的相互距离，我们假设有四个数组

num[i]表示第i个字符串的c的个数

len[i]表示第i个字符串的长度

dist[i]表示第i个串里所有c到最后一个字符的长度（包含c点，原因后面会讲）

dp[i]表示第i个串中所有c相互之间的距离之和，也就是说我们的最终结果是dp[n]

那么显而易见的是num[i]=num[i-1]+num[i-2] len[i]=len[i-1]+len[i-2]

dist[i]=dist[i-1]+dist[i-2]+len[i-1]*num[i-2]

为什么呢？我们假设i-2串是cffffcff i-1串是ffcffcffffcff

那么dist[i-2]代表的即是i-2串中所有c到最后一个字符f的距离，而我们知道我们要求的第i个串中i-2串中的c的距离需要到i-1串中的最后一个字符f，所以我们还需要加上num[i-2]个i-1串的长度，即是len[i-1]*num[i-2] 而对于i-1串的点本来就是到末尾的，所以直接加上就好

dp[i]=dp[i-1]+dp[i-2]+dist[i-2]*num[i-1]+num[i-2]*(len[i-1]*num[i-1]-dist[i-1])

首先加上dp[i-1]和dp[i-2]是毋庸置疑的，那么问题在于我们还需要i-2的字符串中的c到i-1字符串中的c的距离之和。我们可以把这块距离进行分段，比如假设i-2串是cffffcff i-1串是ffcffcffffcff，我们先求i-2串中所有的c点到i-2串最后一个字符的距离，然后再求i-1串第一个字符到i-1串中所有c点的距离。那么，i-2串中所有的c点到i-2串最后一个字符的距离就是dist[i-2]*num[i-1]（从一个c点会出发num[i-1]次），而i-1串第一个字符到所有c点的距离会等于i-1串的长度乘以i-1串中c的个数减去i-1串中c点到最后一个点的距离，这是因为我们可以把第一个字符到最后一个字符的距离拆分成第一个字符到某一个c点，再从c点到最后一个字符。所以从第一个点到所有c点的距离是len[i-1]*num[i-1]-dist[i-1] 最后因为一共会有num[i-2]个点需要求解这段距离，所以乘以num[i-2]即是最终答案。

由于我们把i串分成两个串来算，中间会缺少1的距离，我们只需要在算dist数组的时候把c点也加上就可以了。

注意运算过程中要取模。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 201315
#define mod 530600414
long long num[N],len[N],dp[N],dist[N];
void init()
{
    num[1]=1,num[2]=0,num[3]=1,num[4]=1,num[5]=2;
    len[1]=1,len[2]=2,len[3]=3,len[4]=5,len[5]=8;
    dp[1]=0,dp[2]=0,dp[3]=0,dp[4]=0,dp[5]=5;
    dist[1]=1,dist[2]=0,dist[3]=3,dist[4]=3,dist[5]=11;
    for(int i=6;i<N;i++)
    {
        num[i]=(num[i-1]+num[i-2])%mod;
        len[i]=(len[i-1]+len[i-2])%mod;
        dist[i]=((dist[i-1]+dist[i-2])%mod+(len[i-1]*num[i-2])%mod)%mod;
        dp[i]=((dp[i-1]+dp[i-2])%mod+(dist[i-2]*num[i-1])%mod+((len[i-1]*num[i-1]-dist[i-1])%mod)*num[i-2])%mod;
    }
}
int main()
{
    int T,n;
    init();
    scanf("%d",&T);
    for(int t=1;t<=T;t++)
    {
        scanf("%d",&n);
        printf("Case #%d: %lld\n",t,dp[n]);
    }
    return 0;
}