好贷网好贷款

斐波拉契数列+字符串

发布时间:2016-12-4 20:16:24 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"斐波拉契数列+字符串",主要涉及到斐波拉契数列+字符串方面的内容,对于斐波拉契数列+字符串感兴趣的同学可以参考一下。

Hehe Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1294    Accepted Submission(s): 615 Problem Description As we all know, Fat Brother likes MeiZi every much, he always find some topic to talk with her. But as Fat Brother is so low profile that no one knows he is a rich-two-generation expect the author, MeiZi always rejects him by typing “hehe” (wqnmlgb). You have to believe that there is still some idealized person just like Fat Brother. They think that the meaning of “hehe” is just “hehe”, such like “hihi”, “haha” and so on. But indeed sometimes “hehe” may really means “hehe”. Now you are given a sentence, every “hehe” in this sentence can replace by “wqnmlgb” or just “hehe”, please calculate that how many different meaning of this sentence may be. Note that “wqnmlgb” means “我去年买了个表” in Chinese.   Input The first line contains only one integer T, which is the number of test cases.Each test case contains a string means the given sentence. Note that the given sentence just consists of lowercase letters. T<=100 The length of each sentence <= 10086   Output For each test case, output the case number first, and then output the number of the different meaning of this sentence may be. Since this number may be quite large, you should output the answer modulo 10007.   Sample Input 4 wanshangniyoukongme womenyiqichuqukanxingxingba bulehehewohaiyoushi eheheheh   Sample Output Case 1: 1 Case 2: 1 Case 3: 2 Case 4: 3   Source 2013 Multi-University Training Contest 4   Recommend zhuyuanchen520 /* * Author: ****** * Created Time: 2013/8/31 15:19:05 * File Name: H.cpp * solve: H.cpp */ #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> #include<string> #include<map> #include<stack> #include<set> #include<iostream> #include<vector> #include<queue> //ios_base::sync_with_stdio(false); //#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; #define sz(v) ((int)(v).size()) #define rep(i, a, b) for (int i = (a); i < (b); ++i) #define repf(i, a, b) for (int i = (a); i <= (b); ++i) #define repd(i, a, b) for (int i = (a); i >= (b); --i) #define clr(x) memset(x,0,sizeof(x)) #define clrs( x , y ) memset(x,y,sizeof(x)) #define out(x) printf(#x" %d\n", x) #define sqr(x) ((x) * (x)) typedef long long LL; const int INF = 1000000000; const double eps = 1e-8; const int maxn = 10096; const int mod = 10007; int sgn(const double &x) { return (x > eps) - (x < -eps); } char he[maxn]; LL f[maxn]; int num[maxn]; int used[maxn]; LL ans[maxn]; int main() { //freopen("in.txt","r",stdin); f[0] = f[1] = 1; for(int i = 2;i<=5043;++i) { f[i] = (f[i-1] + f[i - 2])%mod; } int T; scanf("%d",&T); int k = 1; while(T--) { scanf("%s",he); int len = strlen(he); printf("Case %d: ",k++); he[len] = 'w'; clr(num); clr(used); int cnt = 0; for(int i = 0;i<=len;i++) { if(he[i] == 'h') { if(he[i+1] == 'e') { used[i] = used[i+1] = 1; num[cnt]++; i++; }else { ans[cnt] = f[num[cnt]]; cnt++; } }else { if(used[i-1]) { ans[cnt] = f[num[cnt]]; cnt++; } } } //cout<<cnt<<endl; LL Ans = 1; if(cnt == 0) printf("1\n"); else { for(int i = 0;i<cnt;++i) Ans = Ans*ans[i]%mod; printf("%I64d\n",Ans); } } return 0; }  

上一篇:msOS 中分层与注册思想的个人理解
下一篇:avi 文件格式解析

相关文章

相关评论