「ZJOI2020」抽卡

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

令$f_m$表示期望次数，显然$m>0,f_m=\frac{(n-m)f_m+mf_{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,\ldots,a_m$，按照连续$k$个分段，设每段开始点$A_i$

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

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

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

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

令$dp_{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=\empty]$可知，其系数为0

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

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

$dp_{k}=-1,dp_{k+1}=-dp_{k}=1$

$\forall i\in[k+2,2k],dp_i=0$

$dp_{2k+1}=-dp_{k+1}=-1$

$dp_{2k+2}=-dp_{2k+1}=1$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$\displaystyle G_n(x)=\sum_{i=0}^{\frac{n} {k+1} } (-1)^i\binom{n-ik} {i}x^{ik}(1-x)^i$

$\displaystyle G_n(x)=\sum_{i=0}^{\frac{n} {k+1} } \binom{n-ik} {i}x^{ik}(x-1)^i$

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

$F_n(x)=G_n(x)-x^kG_n(n-k)$

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

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

$\displaystyle \sum_{i=l}^{r} \binom{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 ^2n)$

不$sort$有80pts.jpg

代码好看就完事了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#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);
}