【题解】[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;

}

也可能是我的取模过于离谱，这个题竟然有点卡常。

巴特西

【题解】[LNOI2022] 盒

题目分析：

代码：

最新文章

热门文章