专栏文章

题解：P13757 【MX-X17-T6】Selection

RRainbow_qwqCrystal
P13757题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio9tzwa
此快照首次捕获于
2025/12/02 15:43
3 个月前
此快照最后确认于
2025/12/02 15:43
3 个月前
查看原文
先钦定前 kk 个数组大于后 n−kn-k 个数组，最后乘上 (nk)\binom{n}{k}。
钦定前 kk 个数组每个位置的最小值，后 n−kn-k 个要求小于等于这个最小值数组，且由于要严格小于，不能有前 kk 个、后 n−kn-k 个都有等于这个最小值数组的。
那么要求的问题转化为，总方案数，减去“都有等于”的方案数。
总方案数就是拆成每个位置，枚举最小值，为：
(∑i=1v((v−i+1)k−(v−i)k)in−k)m(\sum_{i=1}^v ((v-i+1)^k - (v-i)^k) i^{n-k})^m
这个式子是一个关于 vv 的 n+1n+1 次多项式，不难插值求出。
要减去的部分，枚举前 kk 个、后 n−kn-k 个等于的个数，分别为 i,ji,j。同样拆成每个位置贡献独立，可得：
∑i=1k∑j=1n−k(−1)i+j(ki)(n−kj)(∑z=1vzk−i(v−z+1)n−k−j)m\sum_{i=1}^k\sum_{j=1}^{n-k}(-1)^{i+j}\binom{k}{i}\binom{n-k}{j}(\sum_{z=1}^{v} z^{k-i} (v-z+1)^{n-k-j})^m
现在问题在于对于每个 i,ji,j 求出 ∑z=1vzi(v−z+1)j\sum_{z=1}^{v} z^{i} (v-z+1)^{j}。
设二元 EGF：
F=∑i,j∑z=1vzi(v−z+1)ji!j!xiyjF =\sum_{i,j} \frac{\sum_{z=1}^{v} z^{i} (v-z+1)^{j}}{i!j!} x^i y^j
对两维求导，可得：
dFdx=∑i,j∑z=1vzi+1(v−z+1)ji!j!xiyj\frac{dF}{dx} =\sum_{i,j} \frac{\sum_{z=1}^{v} z^{i+1} (v-z+1)^{j}}{i!j!} x^i y^j
dFdy=∑i,j∑z=1vzi(v−z+1)j+1i!j!xiyj\frac{dF}{dy} =\sum_{i,j} \frac{\sum_{z=1}^{v} z^{i} (v-z+1)^{j+1}}{i!j!} x^i y^{j}
dFdx+dFdy=(v+1)F\frac{dF}{dx} + \frac{dF}{dy} = (v+1) F
提取两边 [xiyj][x^iy^j] 系数：
(v+1)fi,j=(i+1)fi+1,j+(j+1)fi,j+1(v+1)f_{i,j} = (i+1)f_{i+1,j} + (j+1)f_{i,j+1}
据此递推即可 O(n2)O(n^2) 求出所有 fi,jf_{i,j}。初值需要用到 fi,0=∑z=1vzif_{i,0} = \sum_{z=1}^{v}z^i，这是自然数幂和，可以线性插值。
总复杂度 O(n2log⁡m)O(n^2\log m)。
CPP
struct fval{
	vector<modint>x,y;
	void ins(modint X,modint Y){x.pb(X),y.pb(Y);}
	void init(){x.clear(),y.clear();}
	modint val(modint k){
		int n=x.size();
		modint res=0;
		For(i,0,n-1){
			modint s1=1,s2=1;
			For(j,0,n-1)if(i!=j)s1*=(k-x[j]),s2*=(x[i]-x[j]);
			res+=y[i]*s1/s2;
		}
		return res;
	}
}F;


int n,m,k,v;
modint f[4005][4005],sum[8005];

namespace CF{
	// O(k) 
	modint ml[maxn],mr[maxn];
	modint solve(int n,int k){
		if(n<=k+5){
		modint zz=0;
		For(i,1,n)zz+=qpow(i,k);return zz;}
		For(i,0,k+4)ml[i]=mr[i]=0;
		ml[0]=mr[k+3]=1;
		For(i,1,k+2) ml[i]=ml[i-1]*(n-i);
		Rep(i,k+2,1)mr[i]=mr[i+1]*(n-i);
		modint res=0,y=0;
		For(i,1,k+2){
			y+=modint(i)^k;
			modint a=ml[i-1]*mr[i+1];
			modint b=ifac[i-1]*ifac[k+2-i];
			if((k-i)&1)b=-b;
			res+=y*a*b;
		}
		return res;
	}
}

void work(int O)
{
	n=read(),m=read(),k=read(),v=read();
	modint res=0;
	
	modint all=0;
	
	F.init();
	For(vv,1,n+3){
		modint sv=0;
		For(i,1,vv){
			modint tmp=qpow(vv-i+1,k);
			tmp*=(qpow(i,n-k)-qpow(i-1,n-k));
			sv+=tmp;
		}
	//	cout<<"vv,sv "<<vv<<" "<<sv.x<<"\n";
		F.ins(vv,sv);
	}
	
	all=F.val(v);

//	cout<<"all "<<v<<' '<<all.x<<"\n";
//	For(i,1,v){
//		modint tmp=qpow(v-i+1,k);
//		tmp*=(qpow(i,n-k)-qpow(i-1,n-k));
//		all+=tmp;
//	}
	
	res=qpow(all,m);
//	cout<<"res "<<res.x<<"\n";
	
	// need: for i,j, f[i][j]=\sum qpow(v-z,i)*qpow(z,j)
	// (v+1)*f[i][j] = f[i+1][j]*(i+1) + f[i][j+1]*(j+1)
	// f[i][j+1] * (j+1) = 
	auto calc=[&](int i,int j){
//		modint tmp=0;
//		For(z,1,v) tmp+=qpow(v-z+1,i)*qpow(z,j);
		modint tmp=0;
		For(z,1,v) tmp+=qpow(z,i);
		return tmp;
	};
	
	
	
	For(i,0,n){
		f[i][0]=CF::solve(v,i);
		//f[i][0]=calc(i,0);
		if(i==0) f[i][0]=v;
		f[i][0]*=ifac[i];
//		F.init();
//		For(j,1,i+1){
//			sum[j]=sum[j-1]+qpow(j,i);
//		}
//		For(j,0,i+1) F.ins(j,sum[j]);
//		f[i][0]=F.val(v)*ifac[i];
	//	f[i][0]=calc(i,0)*ifac[i];
	//	cout<<"i,0 "<<i<<" "<<0<<" "<<f[i][0].x<<"\n";
	}
	
	For(j,0,n-1){
		For(i,0,n){
			// 
			f[i][j+1]=(f[i][j]*(v+1)-f[i+1][j]*(i+1));
			f[i][j+1]*=iv[j+1];
	//		cout<<"i,j "<<i<<" "<<j+1<<" "<<f[i][j+1].x<<"\n";
		}
	}
	
	For(i,1,k) For(j,1,n-k) {
		modint tmp=0;
		tmp=f[k-i][n-k-j];
		tmp*=fac[k-i]*fac[n-k-j];
	//	For(z,1,v) tmp+=qpow(v-z+1,k-i)*qpow(z,n-k-j);
	//	cout<<"tmp "<<tmp.x<<"\n";
		tmp=qpow(tmp,m);
		tmp*=C(k,i)*C(n-k,j);
		res-=tmp*sign(i+j);
	}
	res*=C(n,k);
	cout<<res.x<<"\n";
}

signed main()
{
	initC(5005);
	int T=read();
	For(_,1,T)work(_);
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...