题解：P12010 【MX-X10-T6】[LSOT-4] 集合

· · 题解

问候出题人环节：直接出{}\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) 的值。分类讨论：

  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}}.

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

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";
}