标签：dots 10 frac CodeForces times leq binom 合集

1838E. Count Supersequences

https://codeforces.com/contest/1838/problem/E

题意

给定 \(n, m, k\)，一个长度为 \(n\) 的序列 \(a = (a_1, a_2, \dots, a_n)\)，满足 \(1 \leq a_i \leq k\)，求有多少个序列 \(b = (b_1, b_2, \dots, b_m)\)，满足 \(a\) 是 \(b\) 的一个子序列，并且 \(1 \leq b_i \leq k\)，答案对 \(10^9 + 7\) 取模。

\(1 \leq n \leq 2 \times 10^5, n \leq m \leq 10^9, 1 \leq k \leq 10^9\)。

题解

Conclusion. 答案只与 \(n, m, k\) 有关，与 \(a\) 无关。

Proof. 空缺

因为答案与 \(a\) 无关，所以我们可以将 \(a\) 看作 \(a' = (1, 1, \dots, 1)\)（\(n\) 个 \(1\)）。

考虑计算不包含 \(a'\) 的个数。

只需要枚举 \(1\) 的个数即可，注意不能超过 \(n - 1\)。

那么不包含 \(a'\) 的方案数就是：

\[\sum_{i = 0}^{n - 1} \binom{m}{i} (k - 1)^{m - i} \]

因为 \(m\) 是 \(10^9\) 级别的，所以考虑递推组合数：

\[\binom{m}{i} = \frac{m!}{i! \times (m - i)!} = \frac{m!}{(i - 1)! \times (m - i + 1)!} \times \frac{m - i + 1}{i} = \frac{m - i + 1}{i} \times \binom{m}{i - 1} \]

所以从 \(\displaystyle \binom{m}{0}\) 开始递推即可。

标签：dots,10,frac,CodeForces,times,leq,binom,合集
From： https://www.cnblogs.com/RB16B/p/17494906.html