「ZJOI2020」抽卡

Sub1: 从 $n$ 张卡中选取钦定的 $m$ 张的期望次数

令 $f_m$ 表示期望次数，显然 $m>0,f_m=\frac{(n-m)f_m+m{f}_{m-1}}{n}+1$

即 $f_0=0,f_m=f_{m-1}+\frac{n}{m}$

即 ${\displaystyle f_m=\sum _{i=1}^m\frac{n}{i}}$

Minmax容斥转化

回到原问题的 $a_1,a_2,\dots ,a_m$ ，按照连续 $k$ 个分段，设每段开始点 $A_i$

我们要求这些 $[A_i,A_i+k)$ 第一次有一个被满足的期望，这难以解决

用一个 $\text{minmax}$ 容斥处理掉

${\displaystyle min\{\mathrm{\exists }{A}_i\mathrm{合}\mathrm{法}\}=(-1{)}^{T+1}\sum _{T\subset S}max\{\mathrm{\forall }i\in T,A_i\mathrm{合}\mathrm{法}\}}$

这个 $\text{max}$ 显然取决于 $A_i$ 并的长度

令 $d{p}_{i,j}$ 表示当前最大的选择点为 $i$ ，选择的总长度为 $j$ ，容易用前缀和优化到 $O(n^2)$

$$$$

优化求解

容易想到对于每个长度 $\ge k$ 的连续段分别求解，然后分治 $\text{NTT}$ 背包合并

此时我们要对于连续 $n$ 个元素可以选择的子问题求解答案生成函数 $F_n(x)$

$$$$

推论：对于某一个长度 $L\in [k+2,2k]$ 的且已经确定都选择的段，其容斥系数为0

考虑此时，收尾两个段必须选择，而中间的段(个数 $>0$ )随意选择

由等式 $\sum T\in S(-1{)}^{|T|}=[S=\text{empty}]$ 可知，其系数为0

观察一下我们能由这个推论得到什么

令 $d{p}_n$ 表示顺次覆盖前 $n$ 个元素的系数

$d{p}_k=-1,d{p}_{k+1}=-d{p}_k=1$

$\mathrm{\forall }i\in [k+2,2k],d{p}_i=0$

$d{p}_{2k+1}=-d{p}_{k+1}=-1$

$d{p}_{2k+2}=-d{p}_{2k+1}=1$

想必睿智的你一定已经发现了， $dp$ 数组 $k+1$ 一循环

实际上根据这个性质的暴力 $dp$ 可以多10pts

由于 $d{p}_{k+1}=1$ ，也可以表示为 $d{p}_i=d{p}_{k+1}\cdot d{p}_{i-k-1}$

因此可以把连续段的前 $k+1$ 个分裂开来，假装不连续

此时，我们可以简单描述为：

每次选择的是一个长度为 $k+1$ 的段

可以覆盖前 $k$ 个，系数为 $-1$

也可以覆盖 $k+1$ 个，系数为 $1$

并且这 $k+1$ 个段不能相交，可以相邻

根据这样的决策，计算系数可以分为两步

$n$ 个元素选出 $i$ 个长度为 $k+1$ 的段，剩下的元素可以分配到这 $i+1$ 个间隔中

方案数为 ${\displaystyle (\genfrac{}{}{0ex}{}{n-i(k+1)+i+1-1}{i+1-1})=(\genfrac{}{}{0ex}{}{n-ik}{i})}$

一开始令这些段都选择前 $k$ 个，然后对于某一些可以额外选择最后一个，乘上 $-x$

由此我们列出 $\text{OGF}$ 表达式

${\displaystyle G_n(x)=\sum _{i=0}^{\frac{n}{k+1}}(-1{)}^i(\genfrac{}{}{0ex}{}{n-ik}{i})x^{ik}(1-x{)}^i}$

${\displaystyle G_n(x)=\sum _{i=0}^{\frac{n}{k+1}}(\genfrac{}{}{0ex}{}{n-ik}{i})x^{ik}(x-1{)}^i}$

注意边界情况是最后 $k$ 个被选的情况不会算进去，因此实际上

$F_n(x)=G_n(x)-x^k{G}_n(n-k)$

考虑如何计算 $G_n(x)$

我们对于所有的 $i$ 分治，分治到区间 $[l,r]$ 时，我们维护的是

${\displaystyle \sum _{i=l}^r(\genfrac{}{}{0ex}{}{n-ik}{i})x^{(i-l)k}(x-1{)}^{(i-l)}}$

这样就能保证分治时，区间内多项式长度为 $O((r-l+1)(k+1))$

合并时，给右区间补上 $x^{(mid-l+1)k}(x-1{)}^{mid-l+1}$ 即可

因此计算 $F_n(x)$ 和合并 $F_n(x)$ 的复杂度均为 $O(n{\log }^{2}n)$

不 $sort$ 有80pts.jpg

代码好看就完事了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
char IO;
int rd(){
	int s=0;
	while(!isdigit(IO=getchar()));
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return s;
}

const int N=1<<18|10,P=998244353;

int n,k;
ll qpow(ll x,ll k=P-2) {
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}

int rev[N],I[N],J[N];
typedef vector <int> V;
void Init(){
	rep(i,J[0]=1,N-1) J[i]=1ll*J[i-1]*i%P;
	I[N-1]=qpow(J[N-1]);
	drep(i,N-1,1) I[i-1]=1ll*I[i]*i%P;
}
int Init(int n){
	int R=1,c=-1;
	while(R<=n) R<<=1,c++;
	rep(i,0,R-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<c);
	return R;
}
void NTT(int n,V &a,int f) {
	static int e[N>>1];
	rep(i,0,n-1) if(i<rev[i]) swap(a[i],a[rev[i]]);
	for(int i=e[0]=1;i<n;i<<=1) {
		ll t=qpow(f==1?3:(P+1)/3,(P-1)/i/2);
		for(int j=i-2;j>=0;j-=2) e[j+1]=(e[j]=e[j>>1])*t%P;
		for(int l=0;l<n;l+=i*2) {
			for(int j=l;j<l+i;++j) {
				int t=1ll*e[j-l]*a[j+i]%P;
				a[j+i]=a[j]-t,Mod2(a[j+i]);
				a[j]+=t,Mod1(a[j]);
			}
		}
	}
	if(f==-1) {
		ll Inv=1ll*I[n]*J[n-1]%P;
		rep(i,0,n-1) a[i]=a[i]*Inv%P;
	}
}

V operator * (V a,V b){
	if(!a.size() || !b.size()) return {};
	int n=a.size()+b.size()-1,R=Init(n);
	a.resize(R),b.resize(R);
	NTT(R,a,1),NTT(R,b,1);
	rep(i,0,R-1) a[i]=1ll*a[i]*b[i]%P;
	NTT(R,a,-1);
	a.resize(n);
	return a;
}
V operator + (V a,V b){
	if(a.size()<b.size()) swap(a,b);
	rep(i,0,b.size()-1) a[i]+=b[i],Mod1(a[i]);
	return a;
}
V operator - (V a,const V &b){
	if(a.size()<b.size()) a.resize(b.size());
	rep(i,0,b.size()-1) a[i]-=b[i],Mod2(a[i]);
	return a;
}

V operator << (V a,const int &x){
	a.resize(a.size()+x);
	drep(i,a.size()-1,x) a[i]=a[i-x];
	rep(i,0,x-1) a[i]=0;
	return a;
}

int C(int n,int m){ return n<0||m<0||n<m?0:1ll*J[n]*I[m]%P*I[n-m]%P; }
V Binom(int n){
	V A(n+1);
	rep(i,0,n) A[i]=(n-i)&1?P-C(n,i):C(n,i);
	return A;
}
V Solve(int n,int l,int r){
	if(l==r) return {C(n-l*k,l)};
	int mid=(l+r)>>1;
	return Solve(n,l,mid)+((Solve(n,mid+1,r)*Binom(mid-l+1))<<(k*(mid-l+1)));
}
V GetG(int n){ return Solve(n,0,n/(k+1)); }
V GetF(int n){ return GetG(n)-(GetG(n-k)<<k); }

vector <V> T;
V Solve(int l=0,int r=T.size()-1){
	if(l==r) return T[l];
	int mid=(l+r)>>1;
	return Solve(l,mid)*Solve(mid+1,r);
}
int A[N];

int main(){
	Init(),n=rd(),k=rd();
	rep(i,1,n) A[i]=rd();
	sort(A+1,A+n+1);
	rep(i,1,n) {
		int j=i;
		while(A[j+1]==A[j]+1) j++;
		if(j-i+1>=k) T.pb(GetF(j-i+1));
		i=j;
	}
	V Res=Solve();
	int s=0,ans=0;
	rep(i,1,Res.size()-1){
		s=(s+1ll*n*I[i]%P*J[i-1])%P;
		ans=(ans+1ll*s*Res[i])%P;
	}
	ans=(P-ans)%P;
	printf("%d\n",ans);
}