题解：P11617 递推

· · 题解

简单题，稍微推推就好了。

题解

主要利用 \sum_{j = 0} ^ n r_j a_{i - j} = 0, \forall i \ge n。 将这个式子的所有 i \ge n 形式累加起来。设收敛数列总和为 ans。

i\j 0 1 \dots n 总和
n r_0 \times a_n r_1 \times a_{n-1} \dots r_n \times a_0 0
n+1 r_0 \times a_{n+1} r_1 \times a_n \dots r_n \times a_1 0
n+2 r_0 \times a_{n+2} r_1 \times a_{n+1} \dots r_n \times a_2 0
\dots \dots \dots \dots \dots 0
总和 r_0 \times (ans-\sum_{i=0}^{n-1} a_i) r_1 \times (ans-\sum_{i=0}^{n-2} a_i) \dots r_n \times ans 0

最关键的是最后一行，最后一行

r_0 \times (ans-\sum_{i=0}^{n-1} a_i) + r_1 \times (ans-\sum_{i=0}^{n-2} a_i) + \dots + r_n \times (ans-0) = 0

整理一下：

ans \times \sum_{i=0}^n r_i = r_0 \times \sum_{i=0}^{n-1}a_i + r_1 \times \sum_{i=0}^{n-2} a_i + \dots + r_n \times 0

因此：

ans = \dfrac{r_0 \times \sum_{i=0}^{n-1}a_i + r_1 \times \sum_{i=0}^{n-2} a_i + \dots + r_n \times 0}{\sum_{i=0}^n r_i}

上下面都算出来，最后乘法逆元算一下乘起来就行了。

代码


// Author: chenly8128
// Created: 2025-01-25 14:07:20

#include <bits/stdc++.h>
#define int long long
const int mod = 998244353;
const int MAXN = 5e3+10;
using namespace std;
inline int read(void) {
    int res = 0;bool flag = true;char c = getchar();
    while (c < '0' || c > '9') {flag ^= (c == '-');c = getchar();}
    while (c >= '0' && c <= '9') {res = (res << 3) + (res << 1) + (c ^ 48);c = getchar();}
    return flag ? res : -res;
}
int qpow (int a,int k) {
    int ans = 1;
    while (k) {
        if (k&1) ans = ans * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return ans;
}
int n,a[MAXN],r[MAXN];
signed main (void) {
    n = read();
    for (int i = 0;i < n;i++) a[i] = read();
    int sum = 0,res = 0,sum2 = 0;
    for (int i = 0;i <= n;i++)
        r[i] = read();
    for (int i = n;i >= 0;i--) {
        sum2 = (sum2 + r[i]) % mod;
        sum = (sum + res * r[i]) % mod;
        res = (res + a[n-i]) % mod;
    }
    printf ("%lld\n",sum * qpow(sum2,mod-2) % mod);
    return 0;
}