自动搬运

查看原文

来自洛谷，原作者为

	Great_Influence **

搬运于2025-08-24 22:07:57，当前版本为作者最后更新于2019-01-03 21:14:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

推式子题。

首先，可以先设$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;
}