题目链接:https://ac.nowcoder.com/acm/contest/923/C
题目大意:


当时自己就找了找三个人前一项和后一项的关系。直接一次差分搞的。

但是当x的幂很大时,是很难找到规律的。
看了看题解:差分有个性质。
对于y=c,可以直接差分求。

跟据差分数组的性质:b[i]=a[i]-[i-1]
定义一:那么对于一个常数的区间修改+c,只要b[i]=c进行前缀和还原就可以了。

定理二:如果对于一个cx的区间修改,我们求一次差分,b[i]=a[i]-a[i-1]
b[i]=cx-c(x-1)=c,那么就是对整个区间+c,利用定义一再求一次差分就ok了,那么就是b[i]=c然后求了两次差分, 用两次前缀和还原。

定理二:如果对于一个cx^2的区间修改,我们求一次差分,b[i]=a[i]-a[i-1]
b[i]=c(x^2-(x-1)^2)=2cx-c,那么就是对整个区间2cx-c,
可以分成对区间一次cx和一次c(x-1),cx可以用定理二求,c(x-1)也可以用定理二求,
不过是b[i+1]=c。因为对(cx)的第1项为cx,对于c(x-1)的第二项等于cx,所以应该在b[i+1]=c。然后三次前缀和还原。
//标程
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
const long long mod=(long long)1e9+7;
long long d1[MAXN],d2[MAXN],d3[MAXN];//1 id id2
int n,m,T,type,pos;
void pre_sum(long long a[])
{
    for(int i=1;i<=n;++i)
    {
        a[i]=(a[i]+a[i-1])%mod;
    }
    return;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        memset(d1,0,sizeof(d1));
        memset(d2,0,sizeof(d2));
        memset(d3,0,sizeof(d3));
        scanf("%d %d",&n,&m);
        while(m--)
        {
            scanf("%d %d",&type,&pos);
            if(type==1)
            {
                d1[pos]++;
            }
            if(type==2)
            {
                d2[pos]++;
            }
            if(type==3)
            {
                d3[pos]++;
                d3[pos+1]++;
            }
        }
        pre_sum(d1);
 
        pre_sum(d2);
        pre_sum(d2);
 
        pre_sum(d3);
        pre_sum(d3);
        pre_sum(d3);
 
        for(int i=1;i<=n;++i)
        {
            printf("%lld%c",(d1[i]+d2[i]+d3[i])%mod,i==n?'\n':' ');
        }
    }
    return 0;
}
//自己的AC代码:
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int mod=1e9+7;
LL a[100005], b[100005], c[100005];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(c, 0, sizeof(c));
        int n, m, x, y;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            if(x==1)
            {
                a[y]++;
            }
            if(x==2)
            {
                b[y]++;
            }
            if(x==3)
            {
                c[y]++;
            }
        }
        for(int i=1;i<=n;i++)
        {
            a[i]=(a[i]+a[i-1])%mod;
        }
        LL f=0;
        for(int i=1;i<=n;i++)
        {
            f=(f+b[i])%mod;
            b[i]=(b[i-1]+f)%mod;
        }
        LL s=0, sc=0;
        for(int i=1;i<=n;i++)
        {
            LL L=c[i];
            c[i]=(c[i]+c[i-1]+2*(s)%mod+sc)%mod;
            s=(s+L+sc)%mod, sc=(sc+L)%mod;
        }
        for(int i=1;i<=n;i++)
        {
            printf("%lld ",(a[i]+b[i]+c[i])%mod);
        }
        printf("\n");
    }

    return 0;
}