【学习笔记】CF1784F Minimums or Medians

首先让$n$乘上$2$。

考虑枚举最终被删除的位置有哪些。$a_i=0$表示这个位置被删除，$a_i=1$表示这个位置被保留，设满足$a_i=0$的前缀长度为$l$（$l$是偶数），$pr{e}_i$表示$a_i$的前缀和，则从左往右对于每个极长的被删除的连续段$[l,r]$，其能够被删除的充要条件是：

• $r-l+1$是偶数
• $pr{e}_r\le n-r\le pr{e}_r+cnt$

注意到式子满足单调性，因此我们只用判断除了前缀外的第一个连续段是否满足上界，以及最后一个连续段是否满足下界。

对于最后一个连续段，注意到$pr{e}_r+n-r=n-2K$，因此可以等价变形成$n-r\ge \frac{n}{2}-K$，即$r\le \frac{n}{2}+K$。这其实从另一个角度更好理解：第$i$次操作删除的数不会超过$\frac{n}{2}+i$（见Alex_Wei的题解）。因此，对于$\frac{n}{2}+K$之后的数一定都是保留的，不会影响答案。

对于第一个连续段，发现$pr{e}_r+cnt=l-1$，因此枚举$l$，得到$r\ge n-l+1$，因此$[l,n-l+1]$全部被删除，而$[n-l+2,\frac{n}{2}+K]$只需满足连续段长度为偶数即可。

最后，我们注意到从$n$个数中选$2k$个数，使得每一段为偶数的方案数为$\left(\genfrac{}{}{0ex}{}{n-k}{k}\right)$，因此枚举$cnt,l$后计算组合数：

• 若$l\le \frac{n}{2}$，则：

$$\sum _{cnt\le K}\sum _{\max (2cnt+2,\frac{n}{2}-K+1)\le l\le \frac{n}{2}}f(K+l-\frac{n}{2}-1,K-cnt-\frac{n}{2}+l-1)$$

其中$f(n,m)=\left(\genfrac{}{}{0ex}{}{n-m}{m}\right)$。

• 若$l>\frac{n}{2}$，则:

$$\sum _{cnt\le K}f(\frac{n}{2}+K-\max (2cnt+1,\frac{n}{2}),K-cnt)$$

对于第二部分，可以$O(n)$计算；对于第一部分，利用$\left(\genfrac{}{}{0ex}{}{i+1}{j}\right)=\left(\genfrac{}{}{0ex}{}{i}{j}\right)+\left(\genfrac{}{}{0ex}{}{i}{j-1}\right)$可以转化为求上指标减少$1$时的答案，而下指标的指针移动是$O(1)$的，因此总复杂度$O(n)$。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define db double
#define inf 0x3f3f3f3f
using namespace std;
const int mod=998244353;
const int N=2e6+5;
ll fac[N],res,sm,ifac[N];
int n,K;
ll fpow(ll x,ll y=mod-2){ll z(1);for(;y;y>>=1){if(y&1)z=z*x%mod;x=x*x%mod;}return z;
}
void init(int n){fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;ifac[n]=fpow(fac[n]);for(int i=n;i>=1;i--)ifac[i-1]=ifac[i]*i%mod;
}
ll binom(int x,int y){if(x<0||y<0||x<y)return 0;return fac[x]*ifac[y]%mod*ifac[x-y]%mod;
}
void add(ll &x,ll y){x=(x+y)%mod;
}
ll f(int n,int m){if(n<0||m<0||n<2*m)return 0;return binom(n-m,m);
}
int l,r;
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>K,n<<=1,init(n);if(K==0||n/2==K){cout<<1;return 0;}l=0,r=K-1,res=1,sm=1;for(int i=1;i<=K;i++){int nl=K-i-n/2+max(2*i+2,n/2-K+1)-1,nr=K-i-1;if(nl<=nr){while(l>nl)add(sm,binom(i-1,--l));while(r<nr)add(sm,binom(i-1,++r));while(l<nl)add(sm,-binom(i-1,l++));while(r>nr)add(sm,-binom(i-1,r--));add(sm,sm),add(sm,binom(i-1,nl-1)),add(sm,-binom(i-1,nr));add(res,sm);}add(res,f(n/2+K-max(2*i+1,n/2),K-i));}cout<<(res+mod)%mod;
}