ARC 128 F Game against Robot 题解

一个很有意思的计数题。

首先观察给定序列能选择的牌需要满足什么性质。

很显然可以转变成网络流的模型，必须满足前\(2k\)个选择的个数不能超过\(k\)张牌。

考虑每张牌的贡献，假设当前为\(x\)，可以将\(\geq x\)的看作1，\(<x\)的看作0 。

然后就转变成了\(0-1\)问题。

可以统计所有可能排列选择的\(1\)的和，也就是选择比\(x\)大的牌的总数。

可以将\(0\)看成\(-1\),pre为前缀和。

然后统计形如:

\[\sum_{pre}\lfloor \max(pre[1],pre[2],pre[3]...pre[n])\rfloor\\ =\sum_{z\geq 1} \sum_{pre}[\exists pre_i\geq 2z] \]

后面那个式子可以看作网格上移动需要触碰一条\(y-x=2z\)的直线。

是一个很经典的组合数。

时间复杂度为\(O(N)\)。

code:

#include<bits/stdc++.h>
#include<atcoder/all>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define rep(a,b) for(int a=0;a<b;++a)
#define LL long long
#define PB push_back
#define POB pop_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
using namespace atcoder;
using mint = modint998244353;
const int MAXN=1e6+1;
mint fact[MAXN],ifact[MAXN];
mint comb(int A,int B){
    return fact[A]*ifact[B]*ifact[A-B];
}
int a[MAXN],n;
mint cnt[MAXN];
mint tmp[MAXN];
int main(){
    fact[0]=1;
    rb(i,1,1000000) fact[i]=fact[i-1]*i;
    ifact[1000000]=1/fact[1000000];
    rl(i,1000000-1,0) ifact[i]=ifact[i+1]*(i+1);
    scanf("%d",&n);
    rb(i,1,n) scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    reverse(a+1,a+1+n);
    tmp[0]=1;
    mint ans=0;
    rb(k,1,n){
        if(k>=2) tmp[k]=tmp[k-2];
        tmp[k]+=comb(n,k);
        cnt[k]=comb(n,k)*k;
        int z=max(2,2*k-n+1);
        if(z%2==1) z++;
		if(k-z>=0)
        cnt[k]-=tmp[k-z];
        z=(z-2)/2;
        cnt[k]-=comb(n,k)*z;
        cnt[k]*=fact[k];
        cnt[k]*=fact[n-k];
        ans+=(cnt[k]-cnt[k-1])*a[k];
//        cout<<k<<" "<<cnt[k].val()<<" "<<endl;
    }
    cout<<ans.val()<<endl;
    return 0;
}