题意

$n$ 个盒子，总共 $S$ 个球，初始状态 $\{a_i\}$ ，盒子之间边权 $w_i$ 表示一个球经过这条边的花费。问对于所有状态花费之和。

$n\leq5\times10^5, S\leq2\times10^6$ 。

题解

这种题就要考虑小贡献，对于每条边的贡献，插板法易得

$$\begin{aligned} &\sum\limits_{i=1}^{n-1}\sum\limits_{j=0}^{s_n}w_i\dbinom{i-1+j}{i-1}\dbinom{n-i-1+s_n-j}{n-i-1}|s_i-j|\\ =&\sum\limits_{i=1}^{n-1}w_i\left(\sum\limits_{j=0}^{s_n}\dbinom{i-1+j}{i-1}\dbinom{n-i-1+s_n-j}{n-i-1}(j-s_i)+2\sum\limits_{j=0}^{s_i}\dbinom{i-1+j}{i-1}\dbinom{n-i-1+s_n-j}{n-i-1}·(s_i-j)\right)\\ \end{aligned}$$

就是要求

$$f(i,\text{lim})=\sum\limits_{j=0}^{\text{lim}}\dbinom{i-1+j}{i-1}\dbinom{n-i-1+s_n-j}{n-i-1} $$

$$\begin{aligned} g(i,\text{lim})=&\sum\limits_{j=0}^{\text{lim}}\dbinom{i-1+j}{i-1}\dbinom{n-i-1+s_n-j}{n-i-1}j\\ =&\sum\limits_{j=0}^{\text{lim}}\dbinom{i-1+j}{i-1}\dbinom{n-i-1+s_n-j}{n-i-1}((i+j)-i)\\ =&\sum\limits_{j=0}^{\text{lim}}\dbinom{i+j}{i}·\dbinom{n-i-1+s_n-j}{n-i-1}i-\sum\limits_{j=0}^{\text{lim}}\dbinom{i-1+j}{i-1}\dbinom{n-i-1+s_n-j}{n-i-1}i \end{aligned}$$

本质相同。

对于 $f(i,\text{lim})$ 的求法，可以考虑递推。从 $\text{lim}$ 转移过来非常简单，直接加上 $j=\lim$ 的方案。对于从 $i$ 转移，可以重新考虑组合，上式是枚举球，那这里枚举盒子

$$f(i,\text{lim})=\sum_{j=i+1}^n\binom{\text{lim}+j-1}{j-1}\binom{s_n-\text{lim}+n-j-2}{n-j-1} $$

转移减去 $j=i+1$ 即可。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 3e6 + 5, mod = 998244353;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n;
	int s[N], w[N];
	int fac[N], inv[N];
	int add(int a, int b) { return a + b > mod? a + b - mod: a + b; }
	int dec(int a, int b) { return a - b < 0? a - b + mod: a - b; }
	int mul(int a, int b) { return 1ll * a * b % mod; }
	int qpow (int a, ll b) {
		int ans = 1;
		for (; b; b >>= 1, a = mul(a, a))
			if (b & 1) ans = mul(ans, a);
		return ans;
	}
	int binom(int n, int m) { return mul(fac[n], mul(inv[m], inv[n - m]));}
	struct Pointer {
		int i, lim, n, s, val;
		Pointer(int n = 1, int s = 0): n(n), s(s) { i = lim = 0; val = binom(n + s - 1, n - 1); }
		void movi () {++i; if (lim != s) val = dec(val, mul(binom(i + lim, i), binom(s - lim + n - i - 1, n - i)));}
		void movlim () {++lim; val = add(val, mul(binom(i + lim, i), binom(s - lim + n - i - 1, n - i - 1)));}
		int to (int I, int Lim) { for (; i < I; movi()); for (; lim < Lim; movlim()); return val;}
	}A, B;
	int main () {
		fac[0] = 1;
		for (int i = 1; i <= N - 5; ++i) fac[i] = mul(fac[i - 1], i);
		inv[N - 5] = qpow(fac[N - 5], mod - 2);
		for (int i = N - 5; i; --i) inv[i - 1] = mul(inv[i], i);
		for (int T = Read(); T--; ) {
			n = Read();
			for (int i = 1; i <= n; i++) s[i] = Read() + s[i - 1];
			for (int i = 1; i < n; i++) w[i] = Read();
			int ans = 0, t1 = binom(s[n] + n - 1, n - 1), t2 = binom(s[n] + n, n);
			A = Pointer(n - 1, s[n]), B = Pointer(n, s[n]);
			for (int i = 1; i < n; ++i) {
				int s1 = A.to(i - 1, s[i]), s2 = B.to(i, s[i]);
				ans = add(ans, mul(w[i], add(dec(mul(i, dec(t2, t1)), mul(s[i], t1)), dec(mul(mul(2, s[i]), s1), mul(mul(i, 2), dec(s2, s1))))));
			}
			printf ("%d\n", ans);
		}
		return 0;
	}
}

int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}