小w的糖果

小w和他的两位队友teito、tokitsukaze准备为大家发点福利，到底发点什么呢？思考良久之后他们三个人准备了很多很多的糖果。他们让n个小朋友们排成一长排并且从左到右依次标号为1,2,3,4,5,6,7,8,9.....n。

三人每次发糖果，都是从某一个位置开始，只把糖果发给这个人以及这个人右侧的所有人。但是他们发糖果的规则有所不同。

1、如果某轮发糖果的是tokitsukaze，她将会从一个位置pos开始，依次向右给每个人1个糖果。

2、如果某轮发糖果的是teito，他将会从一个位置pos开始，依次向右，他将会给他碰到的第一个人发1个糖果，给他碰到的第二个人发2个糖果，给他碰到的第三个人发3个糖果...碰到的第k个人发k个糖果，直到向右走到编号为n的人为止。

3、如果某轮发糖果的是winterzz1，众所周知小w是个大方的人，所以他发的糖最多，他将会从一个位置pos开始，依次向右，它将会给他碰到的第一个人发1个糖果，给他碰到的第二个人发4个糖果，给他碰到的第三个人发9个糖果...碰到的第k个人发 $k^{2}$ 个糖果直到向右走到编号为n的人为止。

发糖的福利一共进行了m轮，现在告诉你这m轮发糖的人和他们该轮发糖的起始位置pos，请你告诉我这m轮发糖结束后1到n每个人手中糖果的数量，为了避免这个数字过大，你只用输出每一个人手中糖的数量 $mod\;10^{9}+7$ 后的结果即可。

第一行是一个正整数T $(1\leqslant T\leqslant10 )$ ，表示有T组测试案例。对于每组案例：
第一行是两个正整数n,m $(1\leqslant n,m\leqslant10^{5} )$ 表示现在有一排n个人并且进行了m轮发糖果。
接下来m行，每行两个正整数type $(1\leqslant type\leqslant 3)$ ,pos $(1\leqslant pos\leqslant n )$ 分别表示该轮发糖果的人，以及这个人开始发糖果的位置。
type=1时发糖果的人为tokitsukaze，type=2时发糖果的人为teito，type=3时发糖果的人为winterzz1。pos表示位置，并且最左边的人pos为1，最右边的人pos为n。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+1; const int mod=1e9+7; ll a[maxn],b[maxn],c[maxn]; void add(ll *d,int n) { for(int i=1;i<=n;++i) d[i]=(d[i]+d[i-1])%mod; } int main() { int T,n,m,type,pos; scanf("%d",&T); while(T--) { scanf("%d %d",&n,&m); for(int i=1;i<=n;++i) a[i]=b[i]=c[i]=0; while(m--) { scanf("%d%d",&type,&pos); if(type==1) a[pos]++; else if(type==2) b[pos]++; else c[pos]++,c[pos+1]++; } add(a,n); for(int i=1;i<=2;++i) add(b,n); for(int i=1;i<=3;++i) add(c,n); for(int i=1;i<=n;++i) printf("%lld%s",(a[i]+b[i]+c[i])%mod,(i==n)?"\n":" "); } }

#include<bits/stdc++.h> using namespace std; long long t,a[3][100005],M=1e9+7; int main(){ scanf("%lld",&t); while(t--){ int n,m,x,y; memset(a,0,sizeof(a)); scanf("%d%d",&n,&m); for(int i=0;i<m;++i){ scanf("%d%d",&x,&y); ++a[x-1][y]; } long long b=0,c=0,d=0,c1=0,d1=0,d2=0,ans; for(int i=1;i<=n;++i){ b=(b+a[0][i])%M; c1=(c1+a[1][i])%M; c=(c+c1)%M; d1=(d1+a[2][i])%M; d=(d+2*d2+d1); d2=(d2+d1); ans=(b+c+d)%M; printf("%lld ",ans); } printf("\n"); } return 0; }

详情