我要把你开盒挂网上。
我们定义一波:
\(s_i = \sum_{j = 1}^{i} a_j\)
那我们确定 \(b\) 后,答案是好算的,我们用 \(z_i\) 表示 \(b\) 的前缀和,就有:
写40分跑路吧。
之后我们考虑每个 \(v_i\) 的贡献,通过挡板发就有:
前一个组合数相当于有 \(j\) 个小球,分为 \(i\) 个集合,集合可以为空。
前一个组合数相当于有 \(S - j\) 个小球,分为 \(n - i\) 个集合,集合可以为空。
之后我们先只看内部的🦁(即第二个求和之后),考虑拆绝对值,就有:
这个式子的含义是先考虑 \(s_i > j\) 的部分,之后我们考虑全体的 \(j - s_i\),它在 \(s_i > j\) 时是负的,所以需要二倍。
我们先解决后面的🦁,后面的等于:
我们利用组合恒等式:
这个把组合数写开就能证明。
原式就等于:
为避免组合数出现负数,我们把前面的 \(j - 1\) 换成 \(j\),就有
之后就该上玄学了,我不会。
我们先算从 \((0, 0)\) 走到 \((n, m)\) 的方案数,显然是 \(C_{n + m}^{n}\),那我们再考虑经过 \((i, j) \to (i + 1, j)\) 的方案数,就有以下恒等式:
把上边那个🦁用下面的形式表示,原式就等于:
这个是好维护的。
然后我们在看之前的前面那个🦁,即:
我们利用同样的手法化简到:
之后我们再上一次同样的玄学。
我们先算从 \((0, 0)\) 走到 \((n, m)\),其中在第 \(p\) 行到第 \(p + 1\) 行时,不超过第 \(q\) 列的方案数,记作 \(f(n, m, p, q)\),就有:
之后我们换个角度理解,相当于在 第 \(q\) 列到 第 \(q + 1\) 列时至少在第 \(p + 1\) 行,就有:
上面两个式子为恒等式
那么原式就相当于:
然后用个类似莫队的东西就做完了,代码如下:
点击查看代码
// Problem: #P3739. 「LNOI2022」盒
// Contest: Hydro
// URL: http://172.20.0.170/d/jzyz/p/P3739
// Memory Limit: 512 MB
// Time Limit: 3000 ms
// Author: Air2011
//
//
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define int long long
#define Air
namespace io{inline int read(){int x;cin>>x;return x;}inline void write(int x){cout<<x;}}
using namespace io;
int n;
const int N = 3e6 + 10, MOD = 998244353;
int a[N], w[N];
int sum[N];
int fac[N];
int inv[N];
int C(int n, int m){if(n < m) return 0;return fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}
int quick_pow(int a, int b){if(!b) return 1;if(b % 2){return a * quick_pow(a, b - 1) % MOD;}else{int temp = quick_pow(a, b / 2);return temp * temp % MOD;}
}
struct Func{int n, m, p ,q;int ans;void pre(int x, int y){n = x;m = y;p = 0;q = 0;ans = C(x + y - 1, y);}int calc(int P, int Q){while(q < Q){q ++;ans += C(p + q, p) * C(n + m - p - q - 1, m - q) % MOD;ans %= MOD;}while(p < P){p ++;ans -= C(p + q, q) * C(n + m - p - q - 1, n - p) % MOD;;ans %= MOD;}return ans;}
}f, g;//拆绝对值void work(){n = read();for(int i = 1; i <= n; i++){a[i] = read();sum[i] = sum[i - 1] + a[i];}for(int i = 1; i < n; i++){w[i] = read();}f.pre(n - 1, sum[n]);g.pre(n, sum[n] - 1);int ans = 0;for(int i = 1; i < n; i++){int cha = 0;cha += i * C(n + sum[n] - 1, n) % MOD; cha %= MOD;cha -= sum[i] * C(n + sum[n] - 1, sum[n]) % MOD; cha = (cha % MOD + MOD) % MOD;if(sum[i] != 0) cha += 2 * sum[i] * f.calc(i - 1, sum[i]) % MOD; cha %= MOD;if(sum[i] != 0) cha -= 2 * i * g.calc(i, sum[i] - 1) % MOD; cha = (cha % MOD + MOD) % MOD;ans += cha * w[i] % MOD; ans %= MOD;}cout << ans << '\n';
}
signed main() {
#ifndef Airfreopen(".in","r",stdin);freopen(".out","w",stdout);
#endifios::sync_with_stdio(false);cin.tie(0);cout.tie(0);fac[0] = inv[0] = 1;for(int i = 1; i < N; i++){fac[i] = fac[i - 1] * i % MOD;}inv[N - 1] = quick_pow(fac[N - 1], MOD - 2);for(int i = N - 2; i >= 1; i--){inv[i] = inv[i + 1] * (i + 1) % MOD;}int TCS = read();while(TCS --){work();} return 0;
}