本文详细解析了清华集训中一道关于组合数学的问题，通过Raney引理转化题目条件，讨论如何从原问题转化为求解特定数列的圆排列数，最终得出解决方案并提供参考程序。
本文将同步发布于：
题目
题意简述
给你牌数为 m + 1 m+1 m+1 的牌堆，其中第 m + 1 m+1 m+1 张为固定的牌，每张牌用一个非负整数 ω \omega ω 表示，表示打出这张牌可以继续抽 ω \omega ω 张牌。
给出所有 ω ≥ 1 \omega\geq 1 ω≥1 的牌的数量 n n n 和 ω i \omega_i ωi，请你求出在总共 m ! m! m! 种情况中，有多少种情况可以抽到最后一张牌（固定的牌）。
题解
数学转化
考虑用数学语言表示题目，即转化合法牌堆需要满足的条件。
定义 sum i = ∑ j = 1 i ω j \texttt{sum}_i=\sum\limits^{i}_{j=1}\omega_j sumi=j=1∑iωj，那么我们可以转化题意条件为
∀ i ∈ [ 1 , m ] , sum i − i ≥ 0 \forall i\in[1,m],\texttt{sum}_i-i\geq 0 ∀i∈[1,m],sumi−i<
最低0.47元/天 解锁文章
扫一扫
770
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
