Jesus Is Here HDU - 5459

本文主要是介绍Jesus Is Here HDU - 5459，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=5459

递推 由第i-2(左)和第i-1(右)个串推第i个串时 左右串内部的答案都已经知道 需要考虑的就是右串中的c结合左串的c会产生多少新的答案 这样除了答案再额外维护两个数组记录每个串的c的下标数量和下标权值之和 具体递推式子见代码

实在智障啊 一开始还考虑循环节 还觉得没啥问题就开始写 到一半才发现串的长度不是能处理的数量级 就是思路太慢太僵硬了

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll M=530600414;ll fib[300010],cnt[300010],sum[300010],ans[300010];void init()
{int i;fib[1]=1,fib[2]=2;for(i=3;i<=300000;i++) fib[i]=(fib[i-2]+fib[i-1])%M;
}void solve()
{int i;cnt[1]=1,sum[1]=1,ans[1]=0;cnt[2]=0,sum[2]=0,ans[2]=0;for(i=3;i<=300000;i++){cnt[i]=(cnt[i-2]+cnt[i-1])%M;sum[i]=(sum[i-2]+sum[i-1]+(fib[i-2]*cnt[i-1])%M)%M;if(sum[i-2]!=0) ans[i]=(ans[i-2]+ans[i-1]+((sum[i-1]+(fib[i-2]*cnt[i-1])%M)*cnt[i-2])%M-(cnt[i-1]*sum[i-2])%M+10ll*M)%M;else ans[i]=(ans[i-2]+ans[i-1])%M;}
}int main()
{int t,cas,n;init();solve();scanf("%d",&t);for(cas=1;cas<=t;cas++){scanf("%d",&n);printf("Case #%d: %lld\n",cas,ans[n]);}return 0;
}/*
9
5
6
7
8
113
1205
199312
199401
201314
*/

 

这篇关于Jesus Is Here HDU - 5459的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---