题解 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)$。 代码: ```cpp #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; } ```