[atARC128F]Game against Robot

为了方便,下文中的$n$是原来的$\frac{n}{2}$

当确定排列$\{p_{i}\}$后,将$a_{i}$按照$p_{i}$从大到小排序,那么机器人即会不断选第一个元素

考虑玩家最后选择的$n$个元素,合法当且仅当$\forall 1\le i\le n,$其在前$2i$个元素至多选$i$个元素

必要性:考虑前$i$轮,机器人选的总在前$2i$个元素中,反之也即玩家至多在前$2i$个元素中选$i$个元素

充分性:每一轮,玩家不断选择第一个要选的元素

若这样的策略不合法,必然是某次机器人选了玩家要选的元素,假设第一次出现此情况是第$i$轮,由策略该元素前恰有$i$个玩家要选的元素和$i-1$个玩家不选的元素,也即前$2i$个元素中有$i+1$个元素,矛盾

反之也即等价于在后$2i$个元素中,至少选$i$个元素,考虑下述过程:

维护可重集$S$(初始为空),从大到小枚举$i\in [1,n]$,将$a_{2i-1},a_{2i}$加入$S$,并取出$S$中最大的元素(至少要再额外选一个),那么$n$次所取出的元素和即是答案

回到原问题,也即对$\{a_{i}\}$的所有排列求上述过程的答案和

将答案转化为$\sum_{x\in Z^{+}}$取出元素$\ge x$的次数,而对于一个确定的$x$,将元素按照是否$\ge x$标记为01,此时仅需考虑一个01序列的答案(取1的次数)

记$cnt_{i}$为后$2i$个位置中1的个数,则答案为$\min_{0\le i\le n}(cnt_{i}+n-i)$

对此进行归纳——

考虑第$i$次取元素时,$S$中已加入了$cnt_{i}$个1、取出了$\min_{0\le j<i}(cnt_{j}+(i-1)-j)$个1(记后者为$s$),显然取出1当且仅当$[cnt_{i}>s]$,进而(新)答案即$s+[cnt_{i}>s]$

代入式子,也即求证$\min_{0\le j\le i}(cnt_{j}+i-j)=s+[cnt_{i}>s]$,两者均可转换为$\min(s+1,cnt_{i})$,显然相等,即得证

交换排列和$x$的枚举顺序,问题即变为:求所有长为$2n$且恰有$k$个1的01序列上述答案之和

(其中$k$为$\ge x$的元素个数,由于01内部也是不同的,最后还要乘上$k!(2n-k)!$)

为了方便处理,对问题做以下变形——

将序列翻转并将0变为-1,记$sum_{i}$为前缀和,则答案为$n+\frac{\min_{0\le i\le n}sum_{i}}{2}$

$n$可以直接统计,后者转化为$-\sum_{x_{0}\in Z^{-}}[\min_{0\le i\le n}sum_{2i}\le 2x_{0}]$,并交换序列和$x_{0}$的枚举顺序

分析奇偶性,若$sum_{2i+1}\le 2x_{0}$则$sum_{2i}\le 2x_{0}$,进而不妨转换为$\min_{0\le i\le 2n}sum_{i}\le 2x_{0}$

简单构造,问题即统计从$(0,0)$到$(2n,2k-2n)$,每一步$x$坐标+1、$y$坐标$\pm 1$且与$x=2x_{0}$有公共点的路径数

这是一个经典问题,通过翻转可得答案为$\begin{cases}{2n\choose k}&(x_{0}\ge k-n)\\{2n\choose k-2x_{0}}&(x_{0}<k-n)\end{cases}$

将其累加,总答案为$\begin{cases}\sum_{k<i\le 2n,i\equiv k(mod\ 2)}{2n\choose i}&(k-n\ge 0)\\(n-k){2n\choose k}+\sum_{2n-k<i\le 2n,i\equiv k(mod\ 2)}{2n\choose i}&(k-n<0)\end{cases}$

两者都可以通过简单预处理快速求出,同时$x$的枚举仅需要考虑$x=a_{i}$的取值

时间复杂度为$o(n)$,可以通过

[atARC128F]Game against Robot
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 1000005
 4 #define mod 998244353
 5 #define ll long long
 6 int n,m,ans,a[N],fac[N],inv[N],sum[N];
 7 int C(int n,int m){
 8     return (ll)fac[n]*inv[m]%mod*inv[n-m]%mod;
 9 }
10 int calc(int k){
11     int ans=(ll)n*C(m,k)%mod;
12     if (k>=n)ans=(ans-sum[k+2]+mod)%mod;
13     else ans=(ans-((ll)(n-k)*C(m,k)+sum[m-k+2])%mod+mod)%mod;
14     return (ll)ans*fac[k]%mod*fac[m-k]%mod;
15 }
16 int main(){
17     fac[0]=inv[0]=inv[1]=1;
18     for(int i=1;i<N;i++)fac[i]=(ll)fac[i-1]*i%mod;
19     for(int i=2;i<N;i++)inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
20     for(int i=1;i<N;i++)inv[i]=(ll)inv[i-1]*inv[i]%mod;
21     scanf("%d",&m),n=(m>>1);
22     for(int i=1;i<=m;i++)scanf("%d",&a[i]);
23     sort(a+1,a+m+1);
24     for(int i=m;i;i--)sum[i]=(sum[i+2]+C(m,i))%mod;
25     for(int i=1;i<=m;i++)
26         if ((i==1)||(a[i]!=a[i-1]))ans=(ans+(ll)(a[i]-a[i-1])*calc(m-i+1))%mod;
27     printf("%d\n",ans);
28     return 0;
29 }
View Code

 

上一篇:二叉树的性质与满二叉树和完全二叉树


下一篇:(联考)noip90