【题解】[LNOI2022] 盒
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
题目分析：
我们可以对每一条边单独计算贡献，这样会发现贡献很好算：
这样就可以直接40跑路了
上面假设 \(s_i\) 为 \(a\) 的前缀和。
发现难算的就是第二个求和里面的那些，所以就考虑单独考虑，第一步肯定是化绝对值，化出来就是这个样子的：
前后其实本质上是一个东西啦，就选后面的去分析吧。
拆开后就是下面这些：
其实这个式子我们是有一种冲动的，就是想把它们化的整齐一点，方便合并同类项，那么关键也就是化一下后面的式子啦。
其实就可以化为：
为了舒服一些，我们设出一个 \(f(n,s,i,k)\)，其代表：
这样我们就可以很轻松地表示出上面这个式子了，即：
其实就是看看怎么把 \(f\) 那个式子变换成这个式子，剩下就不详细说了，这样我们最后的答案就可以表示为：
我们可以发现因为 \(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\) 个小球放在哪个盒子里，最后得到的式子就是：
这个式子就可以解决 \(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;
}
也可能是我的取模过于离谱，这个题竟然有点卡常。