Codeforces Round #138 (Div. 1)
转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove
再一次在DIV1中怒跪~~~果断应该回到DIV2历练历练
A. Bracket Sequence
找出一个子串，而且它的括号匹配是规范的，要求里面的"[]"对数最多，输出任意一解
其实嘛，括号匹配就是一个堆栈模拟，可以想着想着就觉得有好多细节需要考虑，一直不想写
到了最后才写了枚举+栈模拟的，噗。。。结果必要没过嘛
其实没有那么复杂，记录从头到当前位置的[]个数，而且记录堆栈内每一个字符在串中的位置
当出现括号匹配，也就是弹出堆栈的时候就更新一下，注意堆栈为空的情况
#include<iostream>#include<cstdio>#include<map>#include<cstring>#include<cmath>#include<vector>#include<queue>#include<stack>#include<algorithm>#include<set>#define inf 110000000#define M 10005#define N 2005#define Min(a,b) ((a)<(b)?(a):(b))#define Max(a,b) ((a)>(b)?(a):(b))#define pb(a) push_back(a)#define mem(a,b) memset(a,b,sizeof(a))#define LL long long#define MOD 1000000007using namespace std;LL inv[N],c[N],a[N];LL slove(int n,int m){LL ans=1;for(int i=1;i<=m;i++)ans=((ans*inv[i])%MOD*(n-i+1))%MOD;return ans;}int main(){int n,k;while(scanf("%d%d",&n,&k)!=EOF){for(int i=0;i<n;i++)scanf("%I64d",&a[i]);if(k==0){for(int i=0;i<n;i++) printf("%I64d ",a[i]);printf("\n");continue;}inv[0]=inv[1]=1;for(int i=2;i<N;i++)inv[i]=((-MOD/i*inv[MOD%i])%MOD+MOD)%MOD;for(int i=0;i<n;i++)c[i]=slove(i+k-1,i);for(int i=0;i<n;i++){LL ans=0;for(int j=0;j<=i;j++)ans=(ans+a[j]*c[i-j])%MOD;printf("%I64d ",ans);}puts("");}return 0;}