P6059 [加油武汉]居家隔离题解

TheShadow · 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;
}

P6059 [加油武汉]居家隔离 题解