题解：P10005 [集训队互测 2023] 基础寄术练习题

· · 题解

zfr 感觉比较平凡，但是我做不出来，呜呜呜。

发现 f(a) 不好刻画，记 g(a)=\dfrac{\prod a_i}{\prod s_i}。

考虑 P5644 的组合意义，相当于每次选择一个人删掉，删掉第 i 个人的概率是 \frac{a_i}{\sum a_i}，g(a) 即为，在已知 a 的多重集时，按照如上顺序删数，删数的顺序恰为 a 的概率。显然已知 a 的可重集时，所有的概率之和恰为 1，也即 \sum g(a)=\prod \frac{1}{a_i}。

这样我们可以轻易做 k=1 的情况，对每个 \frac{1}{i} 决策选或者不选即可，时间复杂度是 O(nm) 的。

考虑 k=2，肯定会想枚举 a_1，然后我们希望这个序列满足最后一个被删掉的是 1 号选手。

诶看看怎么刻画一个人最后被删掉的概率。诶这不就是 P5644 吗，直接搬过来，钦定一个集合 S 在 1 号选手的后面，那么有系数

(-1)^{|S|}\frac{a_1}{\sum_{u\in S}a_u+a_1}

然后你就 DP 嘛，记 f_{i,j,k,l,t} 是考虑完前 i 个数，已经选择了 k 个数，a_1=t,\sum_{u\in S}a_u=j 的带容斥系数的贡献，转移的时候枚举第 i 个数是否被选到 a 中，以及其选择加入 S 或者不加入 S，直接做即可 O(n^5)。

发现 a_1 没必要记录，分子上的 a_1 直接贡献到系数里面，分母上的 a_1 直接贡献到 j 里面，DP 里面记录有没有选择过 a_1，一遍 DP 就做完了！

时间复杂度 O(n^4)。 ::::info[code]

const int N=1e2+5,inf=1e9+7;
int n,m,k,mod;
int fpow(int a,int b){
    int res=1;
    for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)res=1ll*a*res%mod;
    return res;
}
inline void upd(int& x){if(x>=mod)x-=mod;}
int iv[N*N];
void initfac(){for(int i=1;i<N*N;i++)iv[i]=fpow(i,mod-2);}
int g[N];
void solve1(){
    g[0]=1;
    for(int i=1;i<=m;i++)for(int j=n;j;j--)upd(g[j]+=1ll*g[j-1]*iv[i]%mod);
    printf("%d\n",g[n]);
}       
int f[2][N*N][N][2];
void solve2(){
    f[0][0][0][0]=1;
    for(int i=1,o=1;i<=m;i++,o^=1){
        memset(f[o],0,sizeof f[o]);
        for(int j=0;j<=n*m;j++)for(int k=0;k<=n;k++)for(int l:{0,1}){
            int v=f[o^1][j][k][l];
            if(!v)continue;
            upd(f[o][j+i][k+1][l]+=1ll*(mod-v)*iv[i]%mod);
            upd(f[o][j][k][l]+=v);
            upd(f[o][j][k+1][l]+=1ll*v*iv[i]%mod);
            if(!l)upd(f[o][j+i][k+1][1]+=1ll*i*v%mod);
        }
    }
    int o=m&1,ans=0;
    for(int i=1;i<=n*m;i++)
        upd(ans+=1ll*f[o][i][n][1]*iv[i]%mod);
    printf("%d\n",ans);
}
int main(){
    n=read(),m=read(),k=read(),mod=read();
    initfac();
    if(k==1)solve1();
    if(k==2)solve2();
    return 0;
}
//  Think twice,code once

::::