题解【SR2.7-T1】【天才⑨与数学递推式】

囧仙 · 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 。

题解

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

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 项，有：

&\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}

两式相加，容易得到：

\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 进行操作：
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;
}

题解 【SR2.7-T1】【天才⑨与数学递推式】

题目大意

题解

参考代码

题解【SR2.7-T1】【天才⑨与数学递推式】