CodeForces 408E Curious Array(组合数学+差分)

You've got an array consisting of n integers: a[1], a[2], ..., a[n]. Moreover, there are m queries, each query can be described by three integers l_i, r_i, k_i. Query l_i, r_i, k_i means that we should add to each element a[j], where l_i ≤ j ≤ r_i.

Record means the binomial coefficient, or the number of combinations from yelements into groups of x elements.

You need to fulfil consecutively all queries and then print the final array.

Input

The first line contains integers n, m (1 ≤ n, m ≤ 10⁵).

The second line contains n integers a[1], a[2], ..., a[n] (0 ≤ a_i ≤ 10⁹) — the initial array.

Next m lines contain queries in the format l_i, r_i, k_i — to all elements of the segment l_i... r_i add number (1 ≤ l_i ≤ r_i ≤ n; 0 ≤ k ≤ 100).

Output

Print n integers: the i-th number is the value of element a[i] after all the queries. As the values can be rather large, print them modulo 1000000007 (10⁹ + 7).

Examples

Input

5 1
0 0 0 0 0
1 5 0

Output

1 1 1 1 1

Input

10 2
1 2 3 4 5 0 0 0 0 0
1 6 1
6 10 2

Output

2 4 6 8 10 7 3 6 10 15

题意：给出n个数，m次操作
每次操作给出li，ri，ki
将li-ri的范围里的第j个数加上 

题解：考虑到上面的ki是在每个操作里是不会变的
考虑在杨辉三角中找规律

k=i是k=i-1的前缀和
然后可以考虑差分
在高维进行好差分后一维一维的降下来
注意差分的时候要每一层都差分

代码如下:

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<string>

#include<vector>

#include<cstring>

#include<iostream>

#include<algorithm>

#define mod 1000000007

using namespace std;

long long fac[],inv[],n,m,a[][],sum[][];

long long kasumi(long long a,long long b)

{

    long long ans=1ll;

    while(b)

    {

        if(b&)

        {

            ans=ans*a%mod;

        }

        a=a*a%mod;

        b>>=;

    }

    return ans;

}

long long c(long long a,long long b)

{

    return fac[a]*inv[b]%mod*inv[a-b]%mod;

}

int main()

{

    fac[]=,inv[]=;

    for(int i=; i<=; i++)

    {

        fac[i]=fac[i-]*i*1ll%mod;

    }

    inv[]=kasumi(fac[],mod-);

    for(int i=; i>=; i--)

    {

        inv[i]=inv[i+]*(i+)*1ll%mod;

    }

    scanf("%lld%lld",&n,&m);

    for(int i=; i<n; i++)

    {

        scanf("%lld",&a[][i]);

    }

    long long l,r,k;

    while(m--)

    {

        scanf("%lld%lld%lld",&l,&r,&k);

        l--,k++;

        a[k][l]++;

        for(int i=; i<=k; i++)

        {

            a[i][r]-=c(k-i+r-l-,k-i);

            a[i][r]=(a[i][r]+mod)%mod;

        }

    }

    for(int k=; k>=; k--)

    {

        for(int i=;i<n;i++)

        {

            a[k][i]+=sum[k+][i+];

            a[k][i]%=mod;

        }

        for(int i=;i<n;i++)

        {

            sum[k][i+]+=sum[k][i]+a[k][i];

            sum[k][i+]%=mod;

        }

    }

    for(int i=;i<n;i++)

    {

        printf("%lld ",a[][i]%mod);

    }

}

巴特西

CodeForces 408E Curious Array(组合数学+差分)

最新文章

热门文章