Jesus Is Here
Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 65535/102400 K (Java/Others)
Total Submission(s): 512 Accepted Submission(s): 368
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.
``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, indicating there are T test cases.
Following T lines, each line contain an integer n (3≤n≤201314), as the identifier of message.
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:
where sn as a string corresponding to the n-th message.
Each line contains an integer equaling to:
∑i<j:sn[i..i+2]=sn[j..j+2]=‘‘cff"(j−i) mod
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
这个题真的很难想，但是hdu划分其难度只有2，那么肯定要好好总结一下了。
给出前9项
c
0
ff
0
cff
0
ffcff
0
cffffcff
5
ffcffcffffcff
16
cffffcffffcffcffffcff
88
ffcffcffffcffcffffcffffcffcffffcff
352
cffffcffffcffcffffcffffcffcffffcffcffffcffffcffcffffcff
1552
0
ff
0
cff
0
ffcff
0
cffffcff
5
ffcffcffffcff
16
cffffcffffcffcffffcff
88
ffcffcffffcffcffffcffffcffcffffcff
352
cffffcffffcffcffffcffffcffcffffcffcffffcffffcffcffffcff
1552
题意：si = si-1+si-2 ，问第i个串中所有c距离之和为多少??
设dp[i]代表第i个串中c的距离之和.
那么dp[i] = dp[i-1]+dp[i-2]+Δ
关键是怎么求Δ。
我们设第i个串的长度为 len[i]，那么容易得到 len[i] = len[i-1]+len[i-2] , len[1]=1,len[2]=2;
设第i个串中c的数量为 num[i]，那么也容易得到 num[i]=num[i-2]+num[i-2],num[1]=1,num[2]=0;
接下来是最重要的:我们设dis[i]代表第i个串中所有的c到末尾的距离之和.那么dis[i]=dis[i-1]+dis[i-2]+num[i-2]*len[i-1],dis[1]=0,dis[2]=0,dis[i-1]+dis[i-2]的话不用说,num[i-2]*len[i-1]代表的是第i-2个串的所有的c到第i-1个串末尾的距离之和,那么增量肯定就是加上第i-2个串中所有的c的个数乘上第i-1个串的长度了。
接下来是如何将所有的条件用上了。
分段考虑：
1.考虑将i-2串中所有的c出发"跳跃"到i-2串的末尾,每个c进行num[i-1]次跳跃,所以总距离为dis[i-2]*num[i-1]
2.接下来考虑i-1串所有的c出发跳跃到i-1串的开头，这样是没办法直接求的，我们知道所有的c跳跃到末尾是dis[i-1]，那么假设所有的c跳跃到开头走的总距离是L，那么L+dis[i-1]=len[i-1]*num[i-1]，每个点进行i-2次跳跃，总共的距离是num[i-2]*(len[i-1]*num[i-1]-dis[i-1])
所以最后的结果为dp[i]=dp[i-1]+dp[i-2]+dis[i-2]*num[i-1]+num[i-2]*(len[i-1]*num[i-1]-dis[i-1])
记得碰到-号多加个mod..不然变成负数就错了！
#include<stdio.h> #include<iostream> #include<string.h> #include <stdlib.h> #include<math.h> #include<algorithm> using namespace std; typedef long long LL; const int N = 201320; const LL mod =530600414; LL num[N],len[N],dis[N],dp[N]; void init() { num[1]=1,num[2]=0,num[3]=1,num[4]=1; len[1]=1,len[2]=2,len[3]=3,len[4]=5; dis[1]=dis[2]=0,dis[3]=dis[4]=3; dp[1]=dp[2]=dp[3]=dp[4]=0,dp[5]=5; for(int i=5;i<=201316;i++){ num[i]=(num[i-1]+num[i-2])%mod; len[i]=(len[i-1]+len[i-2])%mod; } for(int i=5;i<=201316;i++){ dis[i]=((dis[i-1]+dis[i-2])%mod+num[i-2]*len[i-1]%mod)%mod; } for(int i=6;i<=201316;i++){ dp[i] = ((dp[i-1]+dp[i-2])%mod+num[i-1]*dis[i-2]%mod+ (len[i-1]*num[i-1]%mod-dis[i-1]+mod)%mod*num[i-2]%mod)%mod; } } int main(){ init(); int tcase; scanf("%d",&tcase); for(int i=1;i<=tcase;i++){ int n; scanf("%d",&n); printf("Case #%d: %lld ",i,dp[n]); } return 0; }