题解 P5178 【求和】

· · 题解

推式子题。

首先，可以先设a_{n+1}=x_0。然后根据杨辉三角可得:

f[i][j]=\begin{cases}0 & ,i\le j\\\sum_{k=0}^j \binom{j}{k} a_{i-k} & ,i>j\end{cases}

然后可以开始化式子了:

ans=\sum_{i=1}^{n+1}\sum_{j=0}^{i-1} f[i][j] =\sum_{i=1}^{n+1}\sum_{j=0}^{i-1}\sum_{k=0}^j \binom{j}{k}a_{i-k} =\sum_{i=1}^{n+1}\sum_{k=0}^{i-1}a_{i-k}\sum_{j=k}^{i-1}\binom{j}{k} =\sum_{i=1}^{n+1}\sum_{k=1}^i a_k\sum_{j=i-k}^{i-1}\binom{j}{i-k} =\sum_{i=1}^{n+1}\sum_{k=1}^i a_k \sum_{j=1}^k \binom{i-j}{i-k} =\sum_{k=1}^{n+1} a_k \sum_{i=k}^{n+1}\sum_{j=1}^k\binom{i-j}{i-k} =\sum_{k=1}^{n+1} a_k \sum_{j=1}^k\sum_{i=0}^{n+1-k}\binom{i+k-j}{i} =\sum_{k=1}^{n+1} a_k \sum_{j=1}^k\sum_{i=0}^{n+1-k}\binom{i+k-j}{k-j} =\sum_{k=1}^{n+1} a_k \sum_{j=1}^k\binom{k-j+n+2-k}{k-j+1} =\sum_{k=1}^{n+1} a_k \sum_{j=1}^k\binom{n-j+2}{k-j+1} =\sum_{k=1}^{n+1} a_k \sum_{j=1}^k\binom{n-j+2}{n-k+1} =\sum_{k=1}^{n+1} a_k \sum_{j=n-k+2}^{n+1}\binom{j}{n-k+1} =\sum_{k=1}^{n+1} a_k[\binom{n+2}{n-k+2}-1]

到了这里之后，就可以O(n)计算初始答案了。我们对后半部分记录前缀和，然后利用前缀和相减即可支持区间修改。

总时间复杂度O(n+m)。

代码:

#include<bits/stdc++.h>
#define Rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define Repe(i,a,b) for(register int i=(a);i>=(b);--i)
#define rep(i,a,b) for(register int i=(a);i<(b);++i)
#define pb push_back
#define mx(a,b) (a>b?a:b)
#define mn(a,b) (a<b?a:b)
typedef unsigned long long uint64;
typedef unsigned int uint32;
typedef long long ll;
using namespace std;

namespace IO
{
    const uint32 Buffsize=1<<15,Output=1<<24;
    static char Ch[Buffsize],*S=Ch,*T=Ch;
    inline char getc()
    {
        return((S==T)&&(T=(S=Ch)+fread(Ch,1,Buffsize,stdin),S==T)?0:*S++);
    }
    static char Out[Output],*nowps=Out;

    inline void flush(){fwrite(Out,1,nowps-Out,stdout);nowps=Out;}

    template<typename T>inline void read(T&x)
    {
        x=0;static char ch;T f=1;
        for(ch=getc();!isdigit(ch);ch=getc())if(ch=='-')f=-1;
        for(;isdigit(ch);ch=getc())x=x*10+(ch^48);
        x*=f;
    }

    template<typename T>inline void write(T x,char ch='\n')
    {
        if(!x)*nowps++='0';
        if(x<0)*nowps++='-',x=-x;
        static uint32 sta[111],tp;
        for(tp=0;x;x/=10)sta[++tp]=x%10;
        for(;tp;*nowps++=sta[tp--]^48);
        *nowps++=ch;
    }
}
using namespace IO;

void file(void)
{
    FILE*DSD=freopen("water.in","r",stdin);
    FILE*CSC=freopen("water.out","w",stdout);
}

const int MAXN=6e5+7;

const int mod=1234567891;

static int n,m;

static int fac[MAXN],inv[MAXN],a[MAXN];

inline int power(int u,int v)
{
    static int sm;
    for(sm=1;v;v>>=1,u=(uint64)u*u%mod)if(v&1)
        sm=(uint64)sm*u%mod;
    return sm;
}

inline void init()
{
    read(n),read(m);
    Rep(i,1,n+1)
    {
        read(a[i]);
        if(a[i]<0)a[i]+=mod;
    }
    fac[0]=1;
    Rep(i,1,n+2)fac[i]=(uint64)fac[i-1]*i%mod;
    inv[n+2]=power(fac[n+2],mod-2);
    Repe(i,n+2,1)inv[i-1]=(uint64)inv[i]*i%mod;
}

static uint32 Pev[MAXN],*pre=Pev+1;

inline uint32 C(int u,int v)
{return u>=v?(uint64)fac[u]*inv[v]%mod*inv[u-v]%mod:0u;}

static uint32 ans;

inline void solve()
{
    pre[0]=C(n+2,1)-1;
    ans=(uint64)a[n+1]*pre[0]%mod;
    Rep(i,1,n)
    {
        pre[i]=(pre[i-1]+C(n+2,n-i+2)-1)%mod;
        ans=(ans+(uint64)a[i]*(C(n+2,n-i+2)-1))%mod;
    }
    write(ans);
    static int l,r,p;
    Rep(i,1,m)
    {
        read(l),read(r),read(p);
        if(p<0)p+=mod;
        ans=(ans+(uint64)(pre[r]-pre[l-1]+mod)*p)%mod;
        write(ans);
        if(i%100000==0)flush();
    }
    flush();

}

int main()
{
    init();
    solve();
    return 0;
}