P10005 基础寄术练习题 题解

· · 题解

首先，这题要求的是前缀和的积的倒数的和，你知道淘米神的树吧？没错，和这题没什么关系（

但这启发我们考虑构造一棵树，使得最后答案和某棵树的拓扑序数挂钩。我们构造一棵“右偏树”，每个点只有最右方的儿子不为叶子，深度为 i 的非叶子结点有 a_{n+1-i} 个叶子儿子，然后按照 bfs 序给它们编号，这样寄术题就被转化为计数题。先枚举总结点数 N，再枚举拓扑序排列，最后考虑有多少种树结构可能存在上述拓扑序。你会发现，这个排列只有前缀最小值可能成为非叶子结点，所以我们理所当然地考虑第一类斯特林数状物。对于一个固定的 N，我们只要求出一个长为 N 的，满足置换环长均在 m 以内且两两不同的排列，然后把每个置换环按其中最小值排序，然后最小值作为非叶子，就一定可以构造出一棵树！所以当 k=1 时，总结点数为 N 的答案就是上述排列的数量除以 N!，由于除了阶乘，这一部分的 dp 甚至不需要记录当前总结点数，复杂度为 O(n^2)！

然后考虑 k=2，我们要做的其实就是把最下面的非叶子节点的子树大小再乘回去。可是，这其实极其困难，因为我们确定完排列置换环长集合后，该如何找到哪个环将来的最小值最大，需要被乘回去呢？这个最小值最大模型，你知道猎人杀吧？没错，和这题没什么关系（

upd：哦好吧，刚才我发现其实它和猎人杀的关系还是很大的，基本是一个容斥思路，原来只有我做那题没用容斥（

但这启发我们进行类似的转化，把这些置换环想象为一些体积不同的人，然后随机枪毙他们，每人每回合被枪毙概率和其体积成正比，我们要求的就是最后被枪毙的人的期望体积。你想到了什么？min-max 容斥！最后被枪毙的人的期望体积不好求，但我们可以求某集合里第一个被枪毙的人的期望体积啊！那么我们在前面 dp 的基础上，额外记录一维，表示当前被 min-max 容斥枚举的集合的总体积，然后此题就做完了！

时间复杂度 O(n^4)，常数也不大（

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#define int long long
#define add(a,b) (a+=(b),a>=mod?a-=mod:0)
#define neg(x) ((x)&1?mod-1:1)
#define Q(a,b) C((a)+(b)-1,(b)-1)
using namespace std;
int inv[407693],mod;
inline int qpow(int n1,int n2){
    int n3=n1,n4=1;
    while(n2){
        if(n2&1)n4*=n3,n4%=mod;
        n3*=n3,n3%=mod;n2>>=1;
    }return n4;
}
inline int mut(initializer_list<int> arg){
    int ret=1;
    for(auto i:arg)ret*=i,ret%=mod;
    return ret;
}
int n,m,k,dp[300][300],pd[2][101][5340],pe[2][101][5340]; 
signed main(){
    scanf("%lld%lld%lld%lld",&n,&m,&k,&mod);
    for(int i=1;i<=9876;i++)inv[i]=qpow(i,mod-2);
    if(k==1){
    dp[0][0]=1;
    for(int i=1;i<=m;i++){
        for(int j=0;j<=i;j++){
            if(j>0)dp[i][j]+=dp[i-1][j-1]*inv[i]%mod;
            dp[i][j]+=dp[i-1][j];
            dp[i][j]%=mod;
        }
    }
    printf("%lld",dp[m][n]);
    }
    else{
        pd[0][0][0]=mod-1;
        for(int i=1;i<=m;i++){
            for(int j=0;j<=i;j++){
                int r=(i+i-j)*j/2;
                for(int h=0;h<=r;h++){
                    pd[~i&1][j][h]%=mod;
                    pe[~i&1][j][h]%=mod;
                    pd[i&1][j][h]+=pd[~i&1][j][h];
                    pe[i&1][j][h]+=pe[~i&1][j][h];
                    pd[i&1][j+1][h]+=pd[~i&1][j][h]*inv[i]%mod;
                    pe[i&1][j+1][h]+=pe[~i&1][j][h]*inv[i]%mod;
                    pd[i&1][j+1][h+i]+=(mod-pd[~i&1][j][h])*inv[i]%mod;
                    pe[i&1][j+1][h+i]+=(mod+mod-pe[~i&1][j][h]-pd[~i&1][j][h]*i%mod*i%mod)*inv[i]%mod;
                    pd[~i&1][j][h]=0;
                    pe[~i&1][j][h]=0;
                }
            }
        }
        int ans=0;
        for(int i=1;i<=(m)*(m+1)/2;i++)ans+=pe[m&1][n][i]*inv[i],ans%=mod;
        printf("%lld",ans);
    }
}