设 \(a\) 数组的前缀和为 \(s_i\),\(b\) 数组的前缀和为 \(t_i\),那么根据模拟费用流或者贪心的思想,每一条边经过的次数即为 \(|s_i-t_i|\),因此非常 trivial 的做法是转换贡献体,枚举每种方案下每条边被经过的次数,然后乘以 \(w_i\) 求和,具体来说:
\[ans=\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|
\]
推一推:
\[ans=\sum\limits_{i=1}^{n-1}w_i·(\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))
\]
发现等价于求以下两个东西:
\[f(i,lim)=\sum\limits_{j=0}^{lim}\dbinom{i-1+j}{i-1}·\dbinom{n-i-1+s_n-j}{n-i-1}
\]
\[g(i,lim)=\sum\limits_{j=0}^{lim}\dbinom{i-1+j}{i-1}·\dbinom{n-i-1+s_n-j}{n-i-1}·j
\]
先考虑对 \(g\) 进行一些转化使其变成与 \(f\) 形式类似的东西:
\[\begin{aligned}
g(i,lim)&=\sum\limits_{j=0}^{lim}\dbinom{i-1+j}{i-1}·\dbinom{n-i-1+s_n-j}{n-i-1}·j\\
&=\sum\limits_{j=0}^{lim}\dbinom{i-1+j}{i-1}·\dbinom{n-i-1+s_n-j}{n-i-1}·((i+j)-i)\\
&=\sum\limits_{j=0}^{lim}\dbinom{i+j}{i}·\dbinom{n-i-1+s_n-j}{n-i-1}·i-\sum\limits_{j=0}^{lim}\dbinom{i-1+j}{i-1}·\dbinom{n-i-1+s_n-j}{n-i-1}·i
\end{aligned}
\]
其中第二步到第三步是吸收恒等式逆用。
\(i\) 是常数,去掉之后发现左右两边左右两边形式都和 \(f\) 类似,因此先考虑怎么求 \(f\)。发现 \(f\) 的组合意义是,有 \((n-1)\times s_n\) 的网格,从左下走到右上,每一步只能向上或向右,问有多少种走法,使得从第 \(i-1\) 列到第 \(i\) 列时经过的那条边的纵坐标 \(\le lim\)。
然后我就死在这里了,像个傻逼一样。
发现虽然 \(f\) 本身没有什么非常简洁的化简式,但是从 \(f(i,lim)\to f(i,lim+1)\) 的变化是容易的,直接加上经过 \((i-1,lim+1)\to (i,lim+1)\) 这条边的方案数即可。\(f(i,lim)\to f(i+1,lim)\) 也不难,发现后者合法的路径集合一定被前者包含,而二者相差的部分恰好都经过了 \((i,lim)\to (i,lim+1)\) 这条边,同样可以 \(O(1)\) 移动指针。而指针移动总次数是 \(O(n+S)\) 的,所以总复杂度也是这个。
const int MAXN=3e6;
const int MOD=998244353;
int fac[MAXN+5],ifac[MAXN+5];
void init_fac(int n){
for(int i=(fac[0]=ifac[0]=ifac[1]=1)+1;i<=n;i++)ifac[i]=1ll*ifac[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*ifac[i]%MOD;
}
int binom(int n,int k){return 1ll*fac[n]*ifac[k]%MOD*ifac[n-k]%MOD;}
int n,s[MAXN+5],w[MAXN+5];
struct solver{
int n,m,p,q,sum;
void init(int N,int M){n=N;m=M;p=0;q=0;sum=binom(N+M-1,N-1);}
void moveP(){++p;if(q!=m)sum=(sum-1ll*binom(p+q,p)*binom(n-p+m-q-1,n-p)%MOD+MOD)%MOD;}
void moveQ(){++q;sum=(sum+1ll*binom(p+q,p)*binom(n-p-1+m-q,n-p-1))%MOD;}
int at(int P,int Q){while(p<P)moveP();while(q<Q)moveQ();return sum;}
}A,B;
void solve(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&s[i]),s[i]+=s[i-1];
for(int i=1;i<n;i++)scanf("%d",&w[i]);
int res=0,T1=binom(s[n]+n-1,n-1),T2=binom(s[n]+n,n);
A.init(n-1,s[n]);B.init(n,s[n]);
for(int i=1;i<n;i++){
int s1=A.at(i-1,s[i]),s2=B.at(i,s[i]);
res=(res+1ll*(1ll*(T2-T1+MOD)*i%MOD-1ll*s[i]*T1%MOD+2ll*s[i]*s1%MOD-2ll*(s2-s1+MOD)*i%MOD+MOD+MOD)*w[i])%MOD;
}
printf("%d\n",res);
}
int main(){init_fac(MAXN);int qu;scanf("%d",&qu);while(qu--)solve();return 0;}