你有一个包含 共 个整数的集合 。你必须执行恰好 ()次操作,每个操作都是以下两种其中之一:
将 中第 个元素删去。
将 中第 个元素删去。(显然 一直是偶数,所以 也一定是整数)
请你统计,通过这些操作可以获得多少个本质不同的最终集合 ?答案对 取模。
Jerry Wen 定理。
考虑什么样的序列有可能得到(找必要条件),不妨关心被删除的数。
考虑被删除的数的连续段,由于每次是删除相邻两个数,所以每个连续段的长度一定是偶数。
不难发现,第一个连续段一定可以被操作一删掉,为了防止算重,不妨钦定第一个连续段是被操作一删掉的。而之后的连续段一定不能被操作一删掉,所以除了第一个之外的连续段都是被操作二删掉的。
继续观察,发现第 次操作时中位数中较大的那个一定是 ,所以被删除的最大的数不超过 。
发现操作二删除连续段有两种方式:
- 型,即不进行操作一,只进行操作二;
- 型,即一二交替;
发现只有第二个连续段可能使用第一种方式删除,且只有这种方式能删去 的数。所以若第二个连续段中第一个数为 且 ,则 一定都在第二个连续段中。
考虑对于所有满足上述加粗条件的连续段集合 ,一定能构造出合法的操作序列:对于 中的每个连续段的右半部分,若中位数中较大的一个在其中则执行操作二,否则执行操作一。
那么只要数这样的 即可。
为了计数方便,设 表示从 个数中选出 个数且这些数构成的所有连续段长度均为偶数的方案数。这相当于从 个数中选出 个,每数再扩充成两个,所以 。
枚举第一段的长度 :
-
首先有可能剩下的所有连续段都是一二交替地删除的,即第二段的第一个数 ,这部分的方案数是 ;
-
若 则第二段的第一个数有可能 ,那么需要枚举 即第二段的第一个数,方案数是:
发现相当于是求 ,注意到 到 两端指针的移动是 的,并且若已知 也可以快速求出 因为 ,那么双指针维护即可;
时间复杂度 ,代码如下:
// Problem: Minimums or Medians
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1784F
// Memory Limit: 500 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <iostream>
#include <cstdio>
int mod;
// fastmod
struct mint
{
int val;
inline mint(){val=0;}
operator int(){return val;}
template<typename T>inline mint(T x){val=(x%mod+mod)%mod;}
inline mint operator-(){return mod-val;}
template<typename T>inline mint operator^(T b)
{
mint tmp=*this,res=1;
for(;b>0;b>>=1,tmp*=tmp) res=b&1?res*tmp:res;
return res;
}
template<typename T>inline mint operator^=(T b){return *this=*this^b;}
inline mint inv(){return this->operator^(mod-2);}
inline mint operator+(mint b){return val+b.val-(val+b.val>=mod?mod:0);}
inline mint operator-(mint b){return val-b.val+(val-b.val<0?mod:0);}
inline mint operator*(mint b){return 1ll*val*b.val%mod;}
inline mint operator/(mint b){return 1ll*val*b.inv().val%mod;}
inline mint operator+=(mint b){return val=val+b.val-(val+b.val>=mod?mod:0);}
inline mint operator-=(mint b){return val=val-b.val+(val-b.val<0?mod:0);}
inline mint operator*=(mint b){return val=1ll*val*b.val%mod;}
inline mint operator/=(mint b){return val=1ll*val*b.inv().val%mod;}
template<typename T>inline mint operator+(T b){return this->operator+(mint(b));};
template<typename T>inline mint operator-(T b){return this->operator-(mint(b));};
template<typename T>inline mint operator*(T b){return this->operator*(mint(b));};
template<typename T>inline mint operator/(T b){return this->operator/(mint(b));};
template<typename T>inline mint operator+=(T b){return this->operator+=(mint(b));};
template<typename T>inline mint operator-=(T b){return this->operator-=(mint(b));};
template<typename T>inline mint operator*=(T b){return this->operator*=(mint(b));};
template<typename T>inline mint operator/=(T b){return this->operator/=(mint(b));};
};
using namespace std;
const int S=10000005;
mint fra[S],inv[S];
int n,k;
inline mint C(int n,int m)
{
if(n<0||m<0||n<m) return 0;
return fra[n]*inv[n-m]*inv[m];
}
inline mint f(int n,int m)
{
return C(n-m,m);
}
int main()
{
mod=998244353;
fra[0]=1;
for(int i=1;i<=S-3;i++) fra[i]=fra[i-1]*i;
inv[S-3]=fra[S-3].inv();
for(int i=S-3;i>=1;i--) inv[i-1]=inv[i]*i;
scanf("%d%d",&n,&k);
mint ans=0;
int lb=1,rb=0,pr=-1;
mint sum=0;
for(int i=0;i<=k;i++)
{
ans+=i==n?(mint)1:f(min(k,k-i*2+n-1),k-i);
if(i*2<n)
{
int L=k-n+i+1,R=k-i-1;
if(pr>=0) sum=sum*2+C(pr,lb-1)-C(pr,rb);
pr++;
while(lb>L) sum+=C(pr,--lb);
while(rb<R) sum+=C(pr,++rb);
while(lb<L) sum-=C(pr,lb++);
while(rb>R) sum-=C(pr,rb--);
ans+=sum;
}
}
printf("%d\n",ans);
return 0;
}