H 小w的糖果 题解

两个简单结论

给定单位操作的差分数组1 0 0 0 … 0.
结论1：对差分位及以后所有数加1的操作，可以由一次前缀和得到1 1 1 1 … 1.
结论2：对差分位及以后各数依次加1,2,…,n的操作，可以由两次前缀和得到1 2 3 4 … n.

两个进阶结论

对于单位操作的差分数组1 0 0 0 … 0.
结论3：该差分数组的三次前缀和数组的通项公式为.
证明：由等差数列的求和公式显然可得该结论.
结论4：该差分数组的四次前缀和数组的通项公式为.
证明：由结论3，该差分数组的四次前缀和数组的通项应为

.

一个重要结论

结论5：给定单位操作的差分数组1 1 0 0 … 0，对差分位及以后各数依次加的操作，可以对差分数组1 1 0 0 … 0求三次前缀和得到.
证明：设对某一差分数组做次前缀和可得目标数列，则目标数列的通项公式为.比对结论3和结论4，发现做三次前缀和得到二阶通项公式，做四次前缀和得到三阶通项公式，可知.由结论3，标准差分数组做三次前缀和得到的数列通项公式为，因此考虑构造令一通项公式，使得.而,，故数列的原始差分数组为0 1 0 0 … 0,将数列与数列的差分数组叠加，得原始差分数组为1 1 0 0 … 0.

AC代码

#include<bits/stdc++.h>
using namespace std;
#define mem(x) memset(x,0,sizeof(x))
const int mod=1e9+7;
const int maxn=1e5+5;
int d1[maxn],d2[maxn],d3[maxn];
int main(){
    int T;
    cin>>T;
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    while(T--){
        int n,m;
        cin>>n>>m;
        int type,pos;
        mem(d1),mem(d2),mem(d3);
        for(int i=1;i<=m;i++){
            cin>>type>>pos;
            if(type==1)d1[pos]++;
            if(type==2)d2[pos]++;
            if(type==3)d3[pos]++,d3[pos+1]++;
        }
        for(int i=1;i<=n;i++){
            d1[i]=(d1[i]+d1[i-1])%mod;
            d2[i]=(d2[i]+d2[i-1])%mod;
            d3[i]=(d3[i]+d3[i-1])%mod;
        }
        for(int i=1;i<=n;i++){
            d2[i]=(d2[i]+d2[i-1])%mod;
            d3[i]=(d3[i]+d3[i-1])%mod;
        }
        for(int i=1;i<=n;i++){
            d3[i]=(d3[i]+d3[i-1])%mod;
        }
        for(int i=1;i<=n;i++){
            cout<<(d1[i]+d2[i]+d3[i])%mod<<" ";
        }
        cout<<endl;
    }
    return 0;
}