专栏文章

题解：P11617 递推

EElysian_Realm
P11617题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqealsi
此快照首次捕获于
2025/12/04 03:23
3 个月前
此快照最后确认于
2025/12/04 03:23
3 个月前
查看原文
一开始并没有什么思路，于是考虑依次写出 an+1,an+2,an+3,...a2na_{n+1},a_{n+2},a_{n+3},...a_{2n} 的递推式：
−r0an+1=r1an+r2an−1+...+rna1-r_0a_{n+1}=r_1a_n+r_2a_{n-1}+...+r_na_1
−r0an+2=r1an+1+r2an+...+rna2-r_0a_{n+2}=r_1a_{n+1}+r_2a_n+...+r_na_2
−r0an+3=r1an+2+r2an+1+...+rna3-r_0a_{n+3}=r_1a_{n+2}+r_2a_{n+1}+...+r_na_3
......
−r0a2n=r1a2n−1+r2a2n−2+...+rnan-r_0a_{2n}=r_1a_{2n-1}+r_2a_{2n-2}+...+r_na_n
发现存在规律，故最后写项数趋近正无穷时的递推式收尾：
−r0aM=r1aM−1+r2aM−2+...+rnaM−n-r_0a_{M}=r_1a_{M-1}+r_2a_{M-2}+...+r_na_{M-n}
其中 MM 趋近于正无穷。
将以上式子合并，可得：
−r0(∑i=n+1Mai)=∑i=1nri×∑i=n+1Mai+(r1+r2+...+rn)an+(r2+r3+...rn)an−1+...+rna1−(r1aM+r2(aM+aM−2)+...+rn(aM+aM−1+...+aM−n))-r_0(\sum_{i=n+1}^{M}{a_i})=\sum_{i=1}^{n}{r_i} \times \sum_{i=n+1}^{M}{a_i}+(r_1+r_2+...+r_n)a_n+(r_2+r_3+...r_n)a_{n-1}+...+r_na_1-(r_1a_M+r_2(a_M+a_{M-2})+...+r_n(a_M+a_{M-1}+...+a_{M-n}))
由于 {ai}\{a_i\} 的所有项之和收敛，故当 MM 趋近于正无穷时，aMa_M 趋近于 00，对所有项之和的影响趋近于 00，故可以忽略 (r1aM+r2(aM+aM−2)+...+rn(aM+aM−1+...+aM−n)(r_1a_M+r_2(a_M+a_{M-2})+...+r_n(a_M+a_{M-1}+...+a_{M-n}) 一项。
为便于理解，下文用 +inf⁡+\inf（即正无穷）替代 MM。
不妨记 ∑i=n+1+inf⁡ai=S1,∑i=1nai=S2,∑j=inri=Ri\sum_{i=n+1}^{+\inf}{a_i} = S_1,\sum_{i=1}^{n}{a_i} = S_2,\sum_{j=i}^{n}{r_i} = R_i。
则原式化简为 (R1+r0)S1=∑i=1nRian+1−i(R_1+r_0)S_1=\sum_{i=1}^{n}{R_ia_{n+1-i}}。
式子中 RiR_i 可以通过前缀和或后缀和 O(n)O(n) 求出，然后由于题目保证答案可以在模 998244353998244353 意义下表示，故可以使用费马小定理求出 (R1+r0)(R_1+r_0) 在模 998244353998244353 意义下的逆元（记为 AA），记 ∑i=1nRian+1−i\sum_{i=1}^{n}{R_ia_{n+1-i}} 为 BB，则在模 998244353998244353 意义下 S1=A×BS_1 = A \times B。 而 S2S_2 可以在 O(n)O(n) 时间内简单求出。
最后答案即为 S1+S2S_1+S_2，时间复杂度 O(n)O(n)，空间复杂度 O(n)O(n)。
PS：记得计算乘积时及时取模。
参考代码：
CPP
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
const ll MOD = 998244353;
ll n;
ll a[5005],b[5005];
ll qpow (ll x,ll y){ // 快速幂
	ll res = 1,xx = x;
	while (y){
		if (y&1) res = res * xx % MOD;
		y /= 2,xx = xx * xx % MOD;
	}
	return res;
}
ll qb[5005],qa[5005];// 用于记录a,b数组的前缀和
int main (){
	cin >> n;
	for (int i = 1;i <= n;i ++)
		cin >> a[i];
	for (int i = 0;i <= n;i ++)
		cin >> b[i];
	qb[0] = b[0];
	for (int i = 1;i <= n;i ++)
		qb[i] = (qb[i-1] + b[i]) % MOD , qa[i] = (qa[i-1] + a[i]) % MOD;
	ll k1 = 0;
	for (int i = 1;i <= n;i ++)
		k1 = (k1 + ((qb[n] - qb[i-1] + MOD) % MOD * a[n + 1 - i] % MOD)) % MOD;
	ll k2 = k1 * qpow (qb[n] , MOD - 2) % MOD;
	ll k3 = (qa[n] - k2 + MOD) % MOD;
	cout << k3;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...