专栏文章

[组合计数] [容斥] [转化] P10005 [集训队互测 2023] 基础寄术练习题

__Cheems
P10005题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miniggwd
此快照首次捕获于
2025/12/02 02:56
3 个月前
此快照最后确认于
2025/12/02 02:56
3 个月前
查看原文
这题很牛，关键转化赛时想到了，但认为太魔怔了就没继续想下去。

k=1k=1

联想除以连乘有什么可能的转化，发现和树的拓扑序计数有所联系，同时也容易处理前缀和这一要素。只需构造大小分别为 aia_i 的菊花，然后按顺序将根连起来即可。
可以放在拓扑序列上对其简化，最终版本为：考虑有 nn 种不同颜色的球，分别有 a1…ana_1\dots a_n 个，考虑依次插入每种颜色的球，则 ii 插入时在序列末尾的概率为 aisi\frac {a_i}{s_i}，因此记 rir_i 为颜色 ii 最右侧位置，则满足 r1<r2⋯<rnr_1<r_2\dots <r_n 的排列占总排列个数的比例，即为 ∏ai∏si\frac {\prod a_i}{\prod s_i}，记作 gPg_P。
在 a1…ana_1\dots a_n 在集合意义下（排序后）相同的情况下，任意排列都会唯一贡献给一种可能的 aa 排列，因此有 ∑∏ai∏si=1\sum \frac {\prod a_i}{\prod s_i}=1，分子为定值，因此答案为 ∑1∏ai\sum \frac {1}{\prod a_i}，容易 O(n2)O(n^2) 背包。

k=2k=2

1∏i>1si=a1∏si\frac {1}{\prod\limits_{i>1} s_i}=\frac {a_1}{\prod s_i}，因此考虑枚举 a1a_1。仿照 k=1k=1，固定 a2…ana_2\dots a_n 的集合，记 PP 为 a2…ana_2\dots a_n 的排列，则 ∑Pa1∏si=∑PgP∏i>1ai\sum\limits_{P}\frac {a_1}{\prod s_i}=\frac{\sum\limits_{P} g_P}{\prod\limits_{i>1} a_i}。考虑怎么求 ∑gP\sum g_P，首先明确定义：满足 r1r_1 为最小值的排列占总排列个数的比例。总排列个数为 (∑a)!∏ai!\frac {(\sum a)!}{\prod a_i!}，前者考虑容斥，钦定 SS 中的元素在 a1a_1 前面，那么有 (−1)∣S∣(∑x∈Sax)!∏x∈Sax!(∑x∈Sax+a1−1a1−1)(∑a∑x∈Sax+a1)(-1)^{|S|}\frac {(\sum\limits_{x\in S} a_x)!}{\prod\limits_{x\in S}a_x!}{{\sum\limits_{x\in S} a_x+a_1-1}\choose {a_1-1}}{{\sum a}\choose {\sum\limits_{x\in S}a_x+a_1}}，化一下式子得到 ∑gP=∑(−1)∣S∣a1a1+∑x∈Sax\sum g_P=\sum(-1)^{|S|}\frac {a_1}{a_1+\sum\limits_{x\in S}a_x}。
那么直接 dp，记 fi,j,kf_{i,j,k} 为考虑前 ii 个元素，SS 总和为 jj，总共选了 kk 个元素的权值和。发现 a1a_1 无需枚举，在转移时加入即可，只需多开一维记录 a1a_1 是否确定。对于分子，转移时直接乘上；对于分母，不妨将 a1a_1 记入 jj 最后除掉。

代码

CPP
#include<bits/stdc++.h>
using namespace std;

const int N = 1e2 + 5, M = 1e4 + 5;
int n, m, op, mod, inv[M << 1];
int F[N][N], f[M][N][2], g[M][N][2];

inline int qstp(int a, int k) {int res = 1; for(; k; a = 1ll * a * a % mod, k >>= 1) if(k & 1) res = 1ll * res * a % mod; return res;}
inline void ADD(int &a, int b) {a += b; a = (a >= mod ? (a - mod) : a);}
signed main(){
    // freopen("sum.in", "r", stdin);
    // freopen("sum.out", "w", stdout);
    cin >> n >> m >> op >> mod;
    inv[0] = 1;
    for(int i = 1; i < M << 1; ++i) inv[i] = qstp(i, mod - 2);
    if(op == 1){
        F[0][0] = 1;
        for(int i = 1; i <= m; ++i){
            F[i][0] = 1;
            for(int j = 1; j <= n; ++j) F[i][j] = 1ll * (F[i - 1][j] + 1ll * F[i - 1][j - 1] * inv[i] % mod) % mod; 
        }
        cout << F[m][n];
    }    
    else{
        f[0][0][0] = 1;
        for(int i = 1; i <= m; ++i){
            for(int j = 0; j <= i * (i - 1) / 2; ++j)
                for(int k = 0; k <= min(i - 1, n); ++k) g[j][k][0] = f[j][k][0], g[j][k][1] = f[j][k][1];
            for(int j = 0; j <= i * (i - 1) / 2; ++j){
                for(int k = 0; k <= min(i - 1, n); ++k){
                    ADD(f[j + i][k + 1][0], 1ll * (mod - g[j][k][0]) * inv[i] % mod);
                    ADD(f[j][k + 1][0], 1ll * g[j][k][0] * inv[i] % mod);
                    ADD(f[j + i][k + 1][1], 1ll * (mod - g[j][k][1]) * inv[i] % mod);
                    ADD(f[j][k + 1][1], 1ll * g[j][k][1] * inv[i] % mod);
                    ADD(f[j + i][k + 1][1], 1ll * g[j][k][0] * i % mod);
                }
            }   
        }
        int ans = 0;
        for(int i = 0; i <= m * (m + 1) / 2; ++i) ADD(ans, 1ll * f[i][n][1] * inv[i] % mod);
        cout << ans;
    }
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...