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

· · 题解

搬运下官方题解。

现有的另一篇题解的做法是将"前缀和积"映射到树的拓扑序数上，两种做法的第一步都是将它转化掉。

以下的 \binom{\sum a_i}{a_1,a_2,\cdots,a_k} 指的是将 \sum a_i 个球，第 i 种有 a_i 个，相同种球都相同，整体排列的不同方案数，此时为 \prod\frac{1}{a_i!}\times(\sum a_i)!。

k=1

分子上的东西我们通常可以通过累加的技巧解决，但是这个题的分母非常神秘，是前缀和积的倒数，因此考虑优先解决分母上的问题。

考虑一个组合模型：有一个序列，有 n 种数，第 i 种有 a_i 个，一共有 \sum a_i 个数，要计算有多大的概率随机重排整个序列，使得对于第 i 种数最后一次出现的位置 R_i，序列 R 单调递增。答案是，考虑倒序确定当前未填数的位置，最后一个必须分给当前数种类最大的，求概率乘法原理即可。写成式子就是：

g(a)=\prod_{i=1}^n\dfrac{a_i}{\sum_{j=1}^i a_j}

bonus：将这个问题高维化之后，就是【CTS2019】随机立方体 的做法，解决方法是相同的。

注意到这种形式就是前缀和积倒数，考虑进一步拓展这个思想，对于一个 a_1<a_2<\cdots<a_n，考虑 a_i 的所有排列的 g(a) 的和。从整体上考虑直接 \sum a_i 个球进行多重集组合数。注意到 R_i 在不考虑具体赋哪种颜色时是存在且唯一的，所以每一种排列都存在贡献。因此一个有序 a_i 的所有排列的 g(a) 的和 =1，即必然存在。整理可得：

\sum_{a'} \dfrac{\prod_{i=1}^n a'_i}{\prod_{i=1}^n s_i}=\left (\prod_{i=1}^n a_i\right )\times \sum_{a'}\dfrac{1}{\prod_{i=1}^n s_i}=1

所以 f(a) 的和是 \dfrac{1}{\prod_{i=1}^{n}a_i}。

$$ \sum_{S\subseteq\lbrace 1,2,\cdots,m\rbrace,|S|=n}\left(\prod_{i\in S}\dfrac{1}{i}\right) $$ 容易用背包 $O(n^2)$ 求解，可以通过子任务 $2$。 ## $k=2

相当于每个序列都有 a_1 的权值。考虑枚举 a_1=val，并且对于给定 S，固定\lbrace a_2,a_3,\cdots,a_n\rbrace=\lbrace1,2,\cdots,m\rbrace\setminus\lbrace val\rbrace=S 的做法。

考虑最终一起统计的时候，每个排列的 R_i 单调递增可以不考虑，但是我们要求 R_1 必须是 R 中最小的。

正难则反，考虑容斥钦定一个集合 T 使得 \forall i\in T,R_i<R_1，容斥系数显然是 (-1)^{|T|}。方案数显然为，T,a_1 内部考虑加上其余的方案数，令 p=\sum_{i\in T}i。贡献为：

\binom{p}{T_1,T_2,\cdots,T_{|T|}}\binom{a_1-1+p}{a_1-1}\binom{\sum_{i=1}^n a_i}{p+a_1,}

逐个理解即可，除以总个数就是多重集组合数之后累计进答案，这个分式化简后为 \dfrac{a_1}{a_1+p}。因此对于固定的 S，求出 \sum_{T\subseteq S}(-1)^{|T|}\frac{a_1}{a_1+\sum_{i\in T}i} 即可。

考虑整体做法，使用 DP 加速枚举子集。设 f_{i,j,k,0/1} 表示：考虑前 i 个数中选，\sum_{t\in T} t=j,|S|=k，a_1 是否已经选入 T 的容斥系数和。将 a_1 扔进分母，最后统计答案时计算即可。

时间复杂度 O(n^4)。


namespace A{
    int f[105][105];
    void solve(){
        f[0][0]=1;
        F(i,1,m) F(j,0,min(i,n)) f[i][j]=add(f[i-1][j],(j==0)?0:(1ll*f[i-1][j-1]*inv[i]%mod));
        printf("%d",f[m][n]);
    }
}
namespace B{
    int f[2][105][10005][2];
    void solve(){
        f[0][0][0][0]=1;
        int ans=0;
        F(i,1,m){
            const int cur=i&1,lst=cur^1;
            F(j,0,n-1)F(k,0,i*m)F(l,0,1){
                f[cur][j][k][l]=f[lst][j][k][l];
                if(j>0) inc(f[cur][j][k][l],1ll*inv[i]*f[lst][j-1][k][l]%mod);
                if(j>0&&k>=i) dec(f[cur][j][k][l],1ll*inv[i]*f[lst][j-1][k-i][l]%mod);
                if(l>0&&k>=i) inc(f[cur][j][k][l],1ll*i*f[lst][j][k-i][0]%mod);
            }
        }
        F(i,1,m*m) inc(ans,1ll*inv[i]*f[m&1][n-1][i][1]%mod);
        printf("%d",ans);
    }
}
void solve(){
    n=read(),m=read(),k=read(),mod=read();
    init(maxn-3);
    if(k==1) return A::solve(),void();
    if(k==2) return B::solve(),void();
}