【题解】[UTPC2024] C.Card Deck
题目链接，感觉是计数神题。
原题的模型是每一步可以选择顶部 k k k 张牌的一个子集 X i X_i Xi(可以为空）放在袋中，求 m m m 轮之后所有可能的袋子里牌所组成的集合的大小之和。考虑进行转化，只考虑前 k k k 张牌，每张牌都有一个属性 t i ∈ { 0 , 1 , ⋯ , m } t_i \in \{0,1,\cdots,m\} ti∈{0,1,⋯,m}。若 t i = 0 t_i = 0 ti=0，表示这张牌永远不会被放入袋子中，否则表示这张牌会在第 t i t_i ti 轮被放入袋子中。若 S j S_j Sj 表示第 j j j 轮后袋子里的数，最后求 ∑ i = 1 m ∣ S j ∣ \sum \limits_{i = 1}^m |S_j| i=1∑m∣Sj∣。
设两个模型为 A , B A,B A,B，下证明两个模型等价。
证明
A → B A \to B A→B
对于 ∀ i ∈ [ 1 , k ] \forall i \in [1,k] ∀i∈[1,k]，若 i ∈ X j i \in X_j i∈Xj 则有 t i = j t_i = j ti=j，否则 t i = 0 t_i = 0 ti=0。B → A B \to A B→A
在进行第 j j j 步前，所有 t i < j t_i < j ti<j 的牌都已经放入袋中，总共有 ∣ { i ∣ t i < j } ∣ |\{i \mid t_i < j\}| ∣{i∣ti<j}∣ 张。由于放入袋中后会进行补位，也就是说我们并不关心补进来的是哪一张真正的原始牌，当进行第 j j j 步前，牌堆的前 k k k 张牌一定存在所有 t i = j t_i = j ti=j 的牌，也就是说第 j j j 步删掉 { i ∣ t i = j } \{i \mid t_i = j\} {i∣ti=j} 是合法操作。
因此可以对每一张牌单独计算贡献。也就是 ∑ i = 1 m ∣ S j ∣ = ∑ i = 1 k 1 t i > 0 = ∑ i = 1 k t i \sum \limits_{i = 1}^m |S_j| =\sum \limits_{i = 1}^k \bold{1}_{t_i > 0} = \sum \limits_{i = 1}^k t_i i=1∑m∣Sj∣=i=1∑k1ti>0=i=1∑kti
。共有 k k k 张牌，所有合法的 { t i } \{t_i\} {ti} 的方案数为 ( m + 1 ) k (m + 1)^k (m+1)k。强制令 t i = j t_i = j ti=j，则这张牌的贡献为 ( m + 1 ) k − 1 (m + 1)^{k - 1} (m+1)k−1。由于 t i ∈ { 0 , 1 , ⋯ , m } t_i \in \{0,1,\cdots,m\} ti∈{0,1,⋯,m}，则这张牌出现在集合里的次数为 ( 0 + 1 + ⋯ + m ) × ( m + 1 ) k − 1 (0 + 1 + \cdots + m) \times (m + 1)^{k - 1} (0+1+⋯+m)×(m+1)k−1，即 m k m + 1 2 \frac{mk^{m + 1}}{2} 2mkm+1。再由于 k k k 张牌等价，所以最后的答案为
k m k m + 1 2 \dfrac{kmk^{m + 1}}{2} 2kmkm+1