题目链接
https://atcoder.jp/contests/abc171/tasks/abc171_f
题目大意
给定一个长度为 \(n\) 的由小写字母组成的字符串 \(s\) ，每次操作任选一个位置插入任意一个小写字母，问进行恰好 \(k\) 次操作之后能得到多少种本质不同的字符串，答案对 \(10^{9} + 7\) 取模。
两个字符串本质不同，当且仅当长度不同或者至少有一个位置上的字母不同。
数据范围
- \(1\le n, k \le 10^{6}\)
解题思路
不难想到，问题等价于有 \(n + k\) 个位置，我们先找出 \(n\) 个位置依次放上字符串 \(s\) 的每一位，然后剩下的 \(k\) 个位置每个随便选一个字母，能得到多少种本质不同的字符串。
很显然，这样简单粗暴的计算会导致答案统计重复。
如果从反向考虑，假设存在一个答案，我们如何通过一一映射的方法让它统计且恰好被统计一次。
考虑到，一个合法的方案，最终得到的长度为 \(n + k\) 的字符串，\(s\) 一定是它的一个子序列，假设最靠前出现的那个子序列对应的位置为 \(p_1, p_2, \cdots, p_n\) 。考虑枚举 \(p_1, p_2, \cdots, p_n\) ，钦定这些位置为最靠前出现的那个子序列， 选取剩下位置的小写字母时不破坏前面的性质，这样我们每个合法的答案只会被最靠前出现的那个子序列统计一次，这样就能不重不漏地统计了。
那么如何保证不破坏前面那条性质呢？
显然，只要在区间 \((0, p_1)\) 上不要选取字母 \(s_{p_1}\) ，区间 \((p_1, p_2)\) 上不要选取字母 \(s_{p_2}\) ，在区间 \((p_2, p_3)\) 上不要选取字母 \(s_{p_3}\) ，在区间 \((p_{i - 1}, p_{i})\) 上不要选取字母 \(s_{p_i}\) 即可。
考虑枚举最后一个放置字母的位置 \(i\) ，根据上面的分析，在 \(i\) 之前的每个空位，都只能选取 \(25\) 个不同的小写字母，在 \(i\) 之后的每个空位，可以选取 \(26\) 个不同的小写字母，所以容易得到最终答案是
$$ \[\begin{aligned} \sum\limits_{i = n} ^ {n + k} \binom{i - 1}{n - 1} 25^{i - n} 26^{n + k - i} \end{aligned}\]$$