自动搬运

查看原文

来自洛谷，原作者为

	VinstaG173 Si Dieu n'existait pas, il faudrait l'inventer.

搬运于2025-08-24 23:12:05，当前版本为作者最后更新于2025-04-01 16:57:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

问候出题人环节：直接出${}\bmod{10^9+7}$ 怎么你了？

记答案为 $f(n,m)$，则对于 $f(n,1)$ 与 $f(n,n)$ （虽然后者在原题中并没有要求，但为了后续计算方便还是列出）的情况均容易发现所有子集都可以任取一个其中元素为代表，共 $\displaystyle\prod_{k=1}^nk^{\binom nk}$ 种方案。以下设 $n>m\ge2$。

首先发现问题具有对称性，$r(U)$ 取任意值的情况都是本质相同的，故不妨设 $r(U)=n$。以下先考虑 $n\in S$ 时 $r(S)$ 的值。分类讨论：

1. $|S|\le n-m+1$，此时可以将 $U$ 划分为 $m$ 个集合，使得其中有一个为 $S$。由题意知 $\exists i,r(A_i)=n$，由于其为划分，故只有 $S\ni n$，因此只可能 $r(S)=n$。由于 $m<n$，我们有 $n-m+1\ge2$，故 $r(\{a,n\})=n,\forall 1\le a\le n-1$。
2. $|S|\ge m+1$，假设 $r(S)\neq n$，则可以将 $S$ 划分为 $m$ 个集合，其中一个为 $\{r(S),n\}$。由题意和 1. 中结论知 $r(S)=r(\{r(S),n\})=n$，矛盾！故 $r(S)=n$。
3. 其余情况，由于 $|S|\le m$，故 $|S|$ 或者只能划分成全为单点集，或者没有划分方案，条件退化，可以任取一个其中元素为代表元且对其他子集的代表元取值无影响。

综上，对于满足 $n\in S$ 的所有子集 $S$ 共有 $\displaystyle\prod_{k=n-m+2}^{m}k^{\binom{n-1}{k-1}}$ 种方案，剩下是 $U'=\{1,\dots,n-1\}$ 的子集，直接归纳，由乘法原理，得递推式：

$$f(n,m)=f(n-1,m)\cdot n\prod_{k=n-m+2}^{m}k^{\binom{n-1}{k-1}}. $$

展开后合并同样底数，由组合数前缀和公式，得到封闭形式：

$$\begin{aligned} f(n,m)&=f(m,m)\cdot\dfrac{n!}{m!}\prod_{k=3}^{m}k^{\sum_{s=m+1}^{\min(n,k+m-2)}\binom{s-1}{k-1}}\\ &=f(m,m)\cdot\dfrac{n!}{m!}\prod_{k=3}^{m}k^{\binom{\min(n,k+m-2)}{k}-\binom{m}{k}}. \end{aligned}$$

组合数在指数上，要${}\bmod{\varphi(p)}$，其中 $\varphi(p)=10^9+86=2\times3\times41\times59\times68899$ 是 square-free 的，用 Lucas 定理然后 CRT 合并即可。时间复杂度 $O(n+m\log m)$。

Code:

#define ll long long
const int ntf=1e9+87;
inline ll qpw(ll x,int v,int mod=ntf){
	ll r=1;while(v){
		(v&1)&&(r=r*x%mod);
		x=x*x%mod,v>>=1;
	}return r;
}

const int p[5]={2,3,41,59,68899};
int v[5];
ll fac[5][70003];
ll fic[5][70003];
ll __C(int i,int m,int k){
	if(m<k)return 0;
	return fac[i][m]*fic[i][k]%p[i]*fic[i][m-k]%p[i];
}ll _C(int i,int m,int k){
	if(m<k)return 0;
	if(m<p[i])return __C(i,m,k);
	return _C(i,m/p[i],k/p[i])*__C(i,m%p[i],k%p[i])%p[i];
}inline ll C(int m,int k){
	if(m<k)return 0;
	ll res=0;
	for(int i=0;i<5;++i)
		res=(res+_C(i,m,k)*v[i])%(ntf-1);
	return res;
}

int n,m,sum;ll ans;
inline void solve(){
	for(int i=0;i<5;++i){
		fac[i][0]=1;
		for(int j=1;j<p[i];++j)
			fac[i][j]=fac[i][j-1]*j%p[i];
		fic[i][p[i]-1]=p[i]-1;
		for(int j=p[i]-1;j;--j)
			fic[i][j-1]=fic[i][j]*j%p[i];
		v[i]=(ntf-1)/p[i]*qpw((ntf-1)/p[i]%p[i],p[i]-2,p[i]);
	}cin>>n>>m;ans=1;
	if(m==1){
		for(int k=2;k<=n;++k)
			ans=ans*qpw(k,C(n,k))%ntf;
		cout<<ans<<"\n";return;
	}for(int k=2;k<=m;++k)
		ans=ans*qpw(k,C(m,k))%ntf;
	for(int i=n;i>m;--i)ans=ans*i%ntf;
	for(int k=3;k<=m;++k){sum=0;
		ans=ans*qpw(k,C(min(k+m-2,n),k)-C(m,k)+ntf-1)%ntf;
	}cout<<ans<<"\n";
}