Tomoyuki MIzuyama 要出 \(n\) 道题,他现在有 \(m\) 个不同的乱码,他非常的阴间,所以他决定先决定先用这群乱码起好第一个题目的名字,之后每个题目都直接从上一个题目名字中找一个子序列当做自己的名字。
现在他想知道,在第 \(i\) 道题目名字长度为 \(a_i\) 的情况下(\(a_1\ge a_2\ge\cdots\ge a_n\)),总共会有多少组不同的题目名字呢?(输出对 \(10^9+7\) 取模的结果)
这道字符串其实是数论。
典型的逆向思维,既然每一个名字都是上一个的(非空)子序列,不妨倒过来看,变成先确定一个字符串,之后往这个串里面插入字符,一共搞 \(n\) 个。
显然字符插入的位置不同就是不同的方案,而我们正好要求方案数,这个时候其实就会想到组合数了。
怎么用组合数?设当前的串长是 \(a_i\),下一个串长是 \(a_{i+1}\)。我们可以用组合数辅助求出根据已知 \(a_i\) 求出 \(a_{i+1}\) 的种类数。
当然很有可能会计算重复,栗子:原串是 \(bxxxb\) 我们可以在第一、二、三个 \(x\) 前面插入 \(x\)(按理说我们会计算 \(3\) 次),但是实际上最后的结果都是 \(bxxxxb\),所以只能算一次,于是重复计算了 \(2\) 次。
那么如何避免这个问题?其实很简单:对于当前串 \(i\) 的每个字符,我们在它前面插入的字符不能与之相同,就可以避免重复的情况(认真体会,真的很巧妙)。
当然,我们在一个串的结尾插入字符就没有限制,因为我们已经保证了前面不同,那么整个字符串必然不可能相同。
所以我们有了这张图:
我们固定住字符串的结尾 \(p\),那么我们前面还有 \(j-1\) 个位置