自动搬运

查看原文

来自洛谷，原作者为

	囧仙 你做东方鬼畜音MAD，好吗？

搬运于2025-08-24 22:32:20，当前版本为作者最后更新于2021-06-06 11:05:45，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题目大意

给定一个数组 $\{K_1,K_2\cdots,K_m\}$ ，由此得到一个递推式：

$$F_t=\sum_{i=1}^m K_i\times F_{t-i} \quad (t> m)$$

现在有 $m$ 次对答案数组 $\{A_i\}$ 的操作。每次给定一个 $\{F_i\}$ 的前 $m$ 项，然后让 $A_a\gets A_a+F_1,A_{a+1}\gets A_{a+1}+F_2\cdots A_{b}\gets A_b+F_{b-a+1}$ 。输出最后的 $A_i$ 。
$1\leq n\le 1\times 10^6;1\le q \leq 1.2 \times 10^5;1 \leq m \leq 15;1 \leq a_i,k_i,c_i,p \leq 10^8$ 。

题解

首先考虑推广题目中的无限数列的生成方式，将它认为是对一个数组的变换操作（类似于代码当中的函数）。比如根据 $A$ 生成这个数列，就记为 $\Xi(A)$ 。生成的数列的第 $i$ 项记为 $\Xi(A)_i$ 。给出以下定义：

$$\Xi(A)_i=\begin{cases} A_i+\sum_{i=1}^kK_i\times \Xi(A)_{n-i+1} & i>0 \cr 0 & i\le 0 \end{cases}$$

要注意的是，这种方法生成的数列并不等价于题面中给出的式子，因为 $\Xi(A)_2$ 的值与 $A_1$ 有关， $\Xi(A)_3$ 的值与 $A_1$ 和 $A_2$ 有关，等等。

对于递推式，有一个很好的性质：假如有两个数组 $\{P_i\}$ 和 $\{Q_i\}$ ，那么有：

$$\Xi(P)+\Xi(Q)=\Xi(P+Q)$$

（其中，两个数列相加表示其对应项分别相加，两个数列相等当且仅当它们每一项都相等）怎么证明呢？

考虑归纳法。显然，对于第 $1$ 项的值是对应相等的，即满足 $\Xi(P)_1+\Xi(Q)_1=\Xi(P+Q)_1$ 。设结论对于前 $k$ 项成立，那么对于第 $n=k+1$ 项，有：

$$\begin{aligned} &\Xi(P)_{n+1}=P_i+\sum_{i=1}^m K_i\times \Xi(P)_{n+1-i}\cr &\Xi(Q)_{n+1}=Q_i+\sum_{i=1}^m K_i\times \Xi(Q)_{n+1-i}\cr \end{aligned}$$

两式相加，容易得到：

$$\begin{aligned} \Xi(P)_{n+1}+\Xi(Q)_{n+1}&=P_i+Q_i+\sum_{i=1}^m K_i\times \Xi(P)_{n+1-i}+\sum_{i=1}^m K_i\times \Xi(Q)_{n+1-i}\cr &=(P_i+Q_i)+\sum_{i=1}^m K_i(\Xi(P)_{n+i-1}+\Xi(Q)_{n+i-1})\cr &=(P_i+Q_i)+\sum_{i=1}^m K_i\times \Xi(P+Q)_{n+i-1}\cr &=\Xi(P+Q)_i \end{aligned}$$

于是对于 $n=k+1$ 仍然成立。所以原命题成立。

这个结论可以启发我们，假如我们要对若干个数组进行 $\Xi$ 操作后相加，那就可以将它们先相加为一个数组 $S$ 后再根据定义求出 $\Xi(S)$ 。

当然，这样做还有两个小问题要解决。

• 首先，使用 $\Xi(F)$ 生成的数列，它的前 $m$ 项并不是 $F$ 的前 $m$ 项。因此我们只要试图对 $F$ 进行改造，构造出一个 $\mathring F$ 使得 $\Xi(\mathring F)$ 的前 $m$ 项恰好为 $F$ 的前 $m$ 项。

  举个例子。比如 $m=3,K=\{1,2,3\}$ ，我们有一个初始序列 $F=\{1,1,4\}$ ，那么有：

  $$\Xi(F)=\{1,2,8,15,37,91,210,503,1196,\cdots\}$$

  然而，我们希望得到的数列应该是：

  $$\{1,1,4,9,20,50,117,277,661,\cdots\}$$

  不过，解决方法很简单：由于我们预先知道实际序列的前 $m$ 项，所以对于 $S$ 的第 $t$ 项，可以计算出第 $1,2,\cdots t-1$ 项对第 $t$ 项的贡献，然后让 $S_t$ 减去这个贡献即可，即：

  $$\mathring F_t=F_t-\sum_{i=1}^{t-1}K_iF_{t-i}$$

• 此外，我们生成的数列都是无穷长的，也就是生成到了 $[a,+\infty)$ 上。但我们只要 $[a,b]$ 这一段。不过，这个问题也很容易处理。我们计算出 $b+1,b+2,\cdots b+m$ 位置上将会生成的值，然后设法在 $S$ 上减去即可。

  首先预处理出 $\Xi(\{1,0,0,\cdots\})$ 的前 $n+m$ 项，记为 $E_i$ 。那么，在 $F$ 上第 $i$ 位的数字 $F_i$ 对 $\Xi(S)$ 第 $j$ 位的贡献就应该是 $E_{j-i}\times F_i$ 。于是可以求出 $G$ ：

  $$G_i=-\sum_{j=1}^m\mathring F_{j}\times E_{b-a+j-i+1} $$

  同理，可以计算出 $\mathring G$ 。最后，对 $S$ 进行操作：

  $$\begin{aligned} S_{a+i-1}&\gets S_{a+i-1}+\mathring F_{i} & 1\le i\le m \cr S_{b+i}&\gets S_{b+i}+\mathring G_{i} & 1\le i\le m \end{aligned}$$

解决了这两个问题，最后的结果就是 $\Xi\{S\}$ 。

参考代码

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int MAXM=15+3,MAXN=1e6+MAXM+3;
int n,m,p,q;
int qread(){
    int w=1,c,ret;
    while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0';
    while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
    return ret*w;
}
int T[MAXN],K[MAXM],D[MAXN],X[MAXM],Y[MAXM],O[MAXM];
int mod(i64 t){return (t%p+p)%p;}
int main(){
    n=qread(),q=qread(),m=qread(),p=qread(); up(1,m,i) K[i]=qread();
    T[0]=1; up(1,n+m,i){
        up(1,m,j) if(i-j>=0) T[i]=mod(1ll*T[i-j]*K[j]+T[i]);
    }
    up(1,q,i){
        int a=qread(),b=qread()+1; up(1,m,j) X[j]=qread(),Y[j]=0;
        dn(m,1,j) up(1,j,k) X[j]=mod(-1ll*X[j-k]*K[k]+X[j]);
        up(1,m,j) up(1,m,k) if(b-a+k-j>=0) Y[k]=mod(-1ll*X[j]*T[b-a+k-j]+Y[k]);
        dn(m,1,j) up(1,j,k) Y[j]=mod(-1ll*Y[j-k]*K[k]+Y[j]);
        up(1,m,j) D[a+j-1]=mod(D[a+j-1]+X[j]),D[b+j-1]=mod(D[b+j-1]+Y[j]);
    }
    up(1,n,i) up(1,m,j) if(i-j>0) D[i]=mod(1ll*D[i-j]*K[j]+D[i]);
    up(1,n,i) printf("%d ",D[i]);
    return 0;
}