「ZJOI2020」抽卡

Posted on Edited on In

「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);
}