自动搬运

查看原文

来自洛谷，原作者为

	chenly8128 God helps those who help themselves.

搬运于2025-08-24 23:08:52，当前版本为作者最后更新于2025-01-26 11:19:15，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

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

题解

主要利用 $\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$
$n+2$	$r_0 \times a_{n+2}$	$r_1 \times a_{n+1}$		$r_n \times a_2$
$\dots$			$\dots$	$\dots$
总和	$r_0 \times (ans-\sum_{i=0}^{n-1} a_i)$	$r_1 \times (ans-\sum_{i=0}^{n-2} a_i)$		$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;
}