题解：P11617 递推

· · 题解

一开始并没有什么思路，于是考虑依次写出 a_{n+1},a_{n+2},a_{n+3},...a_{2n} 的递推式：

-r_0a_{n+1}=r_1a_n+r_2a_{n-1}+...+r_na_1 -r_0a_{n+2}=r_1a_{n+1}+r_2a_n+...+r_na_2 -r_0a_{n+3}=r_1a_{n+2}+r_2a_{n+1}+...+r_na_3 ... -r_0a_{2n}=r_1a_{2n-1}+r_2a_{2n-2}+...+r_na_n

发现存在规律，故最后写项数趋近正无穷时的递推式收尾：

-r_0a_{M}=r_1a_{M-1}+r_2a_{M-2}+...+r_na_{M-n}

其中 M 趋近于正无穷。
将以上式子合并，可得：

-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}))

由于 \{a_i\} 的所有项之和收敛，故当 M 趋近于正无穷时，a_M 趋近于 0，对所有项之和的影响趋近于 0，故可以忽略 (r_1a_M+r_2(a_M+a_{M-2})+...+r_n(a_M+a_{M-1}+...+a_{M-n}) 一项。
为便于理解，下文用 +\inf（即正无穷）替代 M。
不妨记 \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。
则原式化简为 (R_1+r_0)S_1=\sum_{i=1}^{n}{R_ia_{n+1-i}}。
式子中 R_i 可以通过前缀和或后缀和 O(n) 求出，然后由于题目保证答案可以在模 998244353 意义下表示，故可以使用费马小定理求出 (R_1+r_0) 在模 998244353 意义下的逆元（记为 A），记 \sum_{i=1}^{n}{R_ia_{n+1-i}} 为 B，则在模 998244353 意义下 S_1 = A \times B。 而 S_2 可以在 O(n) 时间内简单求出。
最后答案即为 S_1+S_2，时间复杂度 O(n)，空间复杂度 O(n)。
PS：记得计算乘积时及时取模。
参考代码：

#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;
}