![[题解][LNOI2022] 盒](/static/background/161.jpg "[题解][LNOI2022] 盒")
题目分析：
\[ans = \sum_{i=0}^{n-1} w_i \sum_{j=0}^S |j - s_i| \binom{i+j-1}{i-1}\binom{S - j + n - i - 1}{n - i - 1}
\]
这样就可以直接40跑路了
\(s_i\ 为 \(a\ 的前缀和。
发现难算的就是第二个求和里面的那些，所以就考虑单独考虑，第一步肯定是化绝对值，化出来就是这个样子的：
\[\sum_{j=0}^S (j - s_i \binom{i+j-1}{i-1}\binom{S - j + n - i - 1}{n - i - 1} + 2 \times \sum_{j=0}^{s_i} (s_i - j \binom{i+j-1}{i-1}\binom{S - j + n - i - 1}{n - i - 1}
\]
拆开后就是下面这些：
\[s_i \sum_{j=0}^{s_i}\binom{i+j-1}{i-1}\binom{S - j + n - i - 1}{n - i - 1} - \sum_{j=0}^{s_i} j \times \binom{i+j-1}{i-1}\binom{S - j + n - i - 1}{n - i - 1}
\]
其实就可以化为：
\[i \times \sum_{j=0}^{s_i} \binom{i+j-1}{i}\binom{S - j + n - i - 1}{n - i - 1}
\]
\(f(n,s,i,k\，其代表：
\[f(n,s,i,k = \sum_{j=0}^{k}\binom{i+j-1}{i-1}\binom{s - j + n - i - 1}{n - i - 1}
\]
\[\sum_{j=0}^{s_i} \binom{i+j-1}{i}\binom{S - j + n - i - 1}{n - i - 1} = f(n+1,S-1,i-1,s_i+1
\]
其实就是看看怎么把 \(f\ 那个式子变换成这个式子，剩下就不详细说了，这样我们最后的答案就可以表示为：
\[i \times f(n + 1,S - 1,i+1,S-1 - s_i \times f(n,S,i,S + 2 \times s_i \times f(n,S,i,s_i - 2 \times i \times f(n+1,S-1,i+1,s_i-1
\]
\(i,s_i\ 单调递增，所以如果我们可以快速做到由 \(f(n,s,i,k\ 得到 \(f(n,s,i+1,k\ 和 \(f(n,s,i,k+1\ 就可以用线性的复杂度解决问题
可以根据定义直接得到 \(f(n,s,i,k+1\，但是剩下的那个就很难弄了。
\(f\ 一个很神仙的组合意义：\(s\ 个相同的小球放到 \(n\ 个不同的盒子里，要求前 \(i\ 个盒子放的小球总数小于等于 \(k\ 的方案数。
这个根据定义是很好理解的，每次就是枚举前 \(i\ 个盒子放多少个然后一个插板法。
这个意义其实换句话来说就是：从左到右第 \(k+1\ 个小球一定放在大于编号 \(i\ 的盒子里。那么此时如果我们枚举第 \(k+1\ 个小球放在哪个盒子里，最后得到的式子就是：
\[f(n,s,i,k = \sum_{j = i+1}^{n} \binom{j + k - 1}{j-1} \binom{n - j + s - k - 1}{n - j}
\]
\(i\ 的移动了。
这个式子的具体意义就是：\(k\ 个小球放到前 \(j\ 个盒子里，\(s - k - 1\ 个小球放到剩下的 \(n - j + 1\ 个盒子里，这里主要是要注意第 \(j\ 个盒子我们钦定放了第 \(k+1\ 个球，但不一定仅仅是放了这一个。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e6+5;
const int MOD = 998244353;
int fac[N],inv[N],sum[N],w[N];
inline int read({
int x=0,f=1;char ch=getchar(;
while (ch<'0'||ch>'9'{if (ch=='-' f=-1;ch=getchar(;}
while (ch>='0'&&ch<='9'{x=x*10+ch-48;ch=getchar(;}
return x*f;
}
int mod(int x{
if(x < 0 return (x%MOD + MOD%MOD;
else return x % MOD;
}
int binom(int n,int m{
if(n < m || n < 0 || m < 0 return 0;
return mod(fac[n] * mod(inv[m] * inv[n - m];
}
struct fun{
int n,s,i,k,res;
void init(int _n,int _s,int _i,int _k{
n = _n,s = _s,i = _i,k = _k;res = 0;
for(int j=0; j<=k; j++{
res = mod(res + binom(i + j - 1,i - 1 * binom(s - j + n - i - 1,n - i - 1;
}
}
void movei(int x{
if(x <= i return;
for(int j=i+1; j<=x; j++{
res = mod(res - binom(j + k - 1,j - 1 * binom(s - k - 1 + n - j,n - j;
}
i = x;
}
void movek(int x{
if(x <= k return;
for(int j=k+1; j<=x; j++{
res = mod(res + binom(i + j - 1,i - 1 * binom(s - j + n - i - 1,n - i - 1;
}
k = x;
}
}f1,f2,f3,f4;
int power(int a,int b{
int res = 1;
while(b{
if(b & 1 res = mod(res * a;
a = mod(a * a;
b >>= 1;
}
return res;
}
void pre_work(int n{
fac[0] = 1;
for(int i=1; i<=n; i++ fac[i] = mod(fac[i-1] * i;
inv[n] = power(fac[n],MOD-2;
for(int i=n-1; i>=0; i-- inv[i] = mod(inv[i+1] * (i+1;
}
signed main({
// freopen("in.txt","r",stdin;
// freopen("out.txt","w",stdout;
pre_work(3000000;
int T = read(;
while(T--{
int n = read(;
for(int i=1; i<=n; i++{
int a = read(;
sum[i] = sum[i-1] + a;
}
for(int i=1; i<n; i++ w[i] = read(;
int ans = 0,S = sum[n];
f1.init(n+1,S-1,1,S-1;f2.init(n,S,1,S; //只要保证单调增，初值都没啥问题的
f3.init(n,S,1,0;f4.init(n+1,S-1,1,-1;
for(int i=1; i<n; i++{
// printf("%lld %lld %lld %lld\n",f1.res,f2.res,f3.res,f4.res;
int tmp = 0;
f1.movei(i+1;f2.movei(i;f3.movei(i;f3.movek(sum[i];
f4.movei(i+1;f4.movek(sum[i] - 1;
tmp = mod(tmp + i * f1.res;
tmp = mod(tmp - sum[i] * f2.res;
tmp = mod(tmp + 2 * sum[i] * f3.res;
tmp = mod(tmp - 2 * i * f4.res;
ans = mod(ans + w[i] * tmp;
}
printf("%lld\n",ans;
}
return 0;
}
也可能是我的取模过于离谱，这个题竟然有点卡常。