首页 > 代码库 > 51nod1161 Partial Sums
51nod1161 Partial Sums
开始想的是O(n2logk)的算法但是显然会tle。看了解题报告然后就打表找起规律来。嘛是组合数嘛。时间复杂度是O(nlogn+n2)的
#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>using namespace std;#define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define clr(x,c) memset(x,c,sizeof(x))#define ll long longint read(){ int x=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) x=x*10+c-‘0‘,c=getchar(); return x;}const int nmax=5e3+5;const int mod=1e9+7;ll ans[nmax],a[nmax];ll pow(ll x,int n){ ll res=x;--n; while(n){ if(n&1) res=res*x%mod; x=x*x%mod;n>>=1; } return res;}int main(){ int n=read(),m=read();--m; ans[1]=1; rep(i,2,n) ans[i]=ans[i-1]*(i+m-1)%mod*pow(i-1,mod-2)%mod; ll tp,u; rep(i,1,n) a[i]=read(); rep(i,1,n){ tp=0; rep(j,1,i) tp=(tp+ans[j]*a[i-j+1])%mod; printf("%lld\n",tp); } return 0;}
1161 Partial Sums
题目来源： CodeForces
基准时间限制：2 秒 空间限制：131072 KB 分值: 80 难度：5级算法题
收藏
关注给出一个数组A，经过一次处理，生成一个数组S，数组S中的每个值相当于数组A的累加，比如：A = {1 3 5 6} => S = {1 4 9 15}。如果对生成的数组S再进行一次累加操作，{1 4 9 15} => {1 5 14 29}，现在给出数组A，问进行K次操作后的结果。(每次累加后的结果 mod 10^9 + 7)
Input
第1行，2个数N和K，中间用空格分隔，N表示数组的长度，K表示处理的次数（2 <= n <= 5000, 0 <= k <= 10^9, 0 <= a[i] <= 10^9)
Output
共N行，每行一个数，对应经过K次处理后的结果。每次累加后mod 10^9 + 7。
Input示例
4 21356
Output示例
151429
51nod1161 Partial Sums
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。