自动搬运

查看原文

来自洛谷，原作者为

	TheShadow **

搬运于2025-08-24 22:16:59，当前版本为作者最后更新于2020-02-08 16:52:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目链接

P6059 [加油武汉]居家隔离

Solution

**以下分析时，默认轮数为 $m$ **。

先分析一下算法大概的框架。

时间复杂度要求是 $O(n^2)$ ，然而我们需要求出对于每一个 $i\in[1,n-1]$ 的答案，这个我们显然是要枚举的，所以对于每一个 $i$ 我们需要 $O(n)$ 算出答案。

然后我们注意到决策中有一个很重要的分解点 $x_k$ ，我们可以尝试枚举这个数是多少。

我们通过期望的定义来计算这道题，即 $E=\frac{res}{sum}$ ，其中 $res,sum$ 分别是指所有方案下答案的总和与方案数。

这道题我们可以看做是对原序列的所有排列来求答案，所以方案数为 $n!$ 。

当 $k\in[m,n-1]$ 时。

最后的答案显然是 $x_j,j\in[k+1,n]$ 。

考虑答案是 $x_j$ 时的方案数（我们将它称作贡献），可以发现此时 $x_j$ 是后几个数中最先出现的 。

因为前 $m$ 个数中最大的是 $x_k$ ，所以前 $m$ 个数的选取方案为 $\binom{k-1}{m-1}$ ，考虑顺序，再乘上 $m!$ 。

考虑 $[1,k]$ 中剩下的 $k-m$ 个数，他们一定不会成为答案，所以可以随意放置，方案数为 $\binom{n-m}{k-m}$ ，考虑顺序，再乘上 $(k-m)!$ 。

由于 $x_j$ 是最先出现的，所以剩下的 $n-k$ 个位置中，它一定在最前面，其他的 $n-k-1$ 个数考虑顺序，贡献再乘上 $(n-k-1)!$ 。

可以发现贡献与 $j$ 无关，所以我们通过前缀和优化即可 $O(1)$ 计算分界值为 $x_k$ 时的答案。

当 $k=n$ 时。

这时显然不存在 $x>x_k$ ，所以答案就是最后一个取到的数。

我们假设答案是 $x_j$ ，那么我们首先需要从剩下的 $n-1$ 个数中选出前 $m$ 个，因为最后一个必选，所以贡献乘上方案数 $\binom{n-2}{m-1}$ 。

考虑这选出来的 $m$ 个数的顺序，贡献乘上 $m!$ 。

由于默认 $x_j$ 是最后一个，考虑剩下的数的顺序，贡献乘上 $(n-m-1)!$ 。

由于对每一个 $x_j,j\in[1,n-1]$ ，贡献均相同，所以通过前缀和即可 $O(1)$ 算出。

综上，我们得到了一个 $O(n^2)$ 的算法，可以通过本题。

Code

#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define INF 0x3f3f3f3f
#define lowbit(x) (x&(-x))
#define mid ((l+r)>>1)
using namespace std;
template<class T>il read(T &x){
	x=0;int f=1;char k=getchar();
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=x*10+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x>9) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
it qpow(int x,int k,int mod){
	int res=1,bas=x;
	while(k){
		if(k&1) res=1ll*res*bas%mod;
		bas=1ll*bas*bas%mod,k>>=1;
	}
	return res;
}
const int N = 1e3+5,mod = 998244353;
int n,fac[N],ifac[N],val[N],sum[N];
it add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
it mul(int x,int y){return 1ll*x*y%mod;}
il inc(int &x,int y){x=add(x,y);}
it C(int n,int m){return m>n?0:mul(mul(ifac[m],ifac[n-m]),fac[n]);}
il Solve(int m){
	int res=0,div=fac[n];
	for(ri i=m;i<n;++i){
		int tval=add(sum[n],mod-sum[i]);
		tval=mul(tval,C(i-1,m-1));
		tval=mul(tval,C(n-m,i-m));
		tval=mul(tval,fac[m]);
		tval=mul(tval,fac[i-m]);
		tval=mul(tval,fac[n-i-1]);
		inc(res,tval);
	}
	int tval=mul(C(n-2,m-1),fac[m]);
	tval=mul(tval,sum[n-1]);
	tval=mul(tval,fac[n-m-1]);
	inc(res,tval);
	print(mul(res,qpow(div,mod-2,mod))),putchar(' ');
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),fac[0]=1;
	for(ri i=1;i<=n;++i) fac[i]=mul(fac[i-1],i);
	ifac[n]=qpow(fac[n],mod-2,mod);
	for(ri i=n-1;i>=0;--i) ifac[i]=mul(ifac[i+1],i+1);
	for(ri i=1;i<=n;++i) read(val[i]);
	sort(val+1,val+1+n);
	for(ri i=1;i<=n;++i) sum[i]=add(sum[i-1],val[i]);
	for(ri i=1;i<n;++i)
		Solve(i);
	return 0;
}