CF1838E

题面传送门

description

给定长度为 \(n\) 的正整数序列 \(a\) 和正整数 \(m,k\)，满足 \(a\) 的值域是 \([1,k]\)。求 \(a\) 是多少个长度为 \(m\) 且值域为 \([1,k]\) 的序列 \(b\) 的子序列。

• \(n\leq 2\times 10^5\)

• \(m,k\leq 10^9\)

solution

考虑通过序列 \(a\) 构造序列 \(b\)。在每个 \(a_i\) 前面放置若干个（可能是 0 个）\([1,k]\) 中的正整数，并且 \(a_{i-1}\) 至 \(a_i(i>1)\) 中间不能有值为 \(a_i\) 的值出现，对于 \(a_n\) 后面的数，任意放。这样我们可以做到不重不漏，因为这种构造使我们从 \(b\) 序列里尽可能靠前地取出 \(a\) 序列中的元素。

枚举 \(a_n\) 之前新插入的数的个数 \(i\)，每个数都有 \(k-1\) 种取值，则 \(a_n\) 之前放数的方案数用插板法不难算出为 \((k-1)^i\dbinom{n+i-1}{n-1}\)，又因为 \(a_n\) 后面有 \(m-n-i\) 个数，每个数有 \(k\) 种取值，所以答案为 \(\sum\limits_{i=0}^{m-n} k^{m-n-i}(k-1)^{i}\dbinom{n+i-1}{n-1}\)。

直接计算是 \(O(m-n)\approx O(m)\) 的，考虑把式子变变形。

令 \(x=k-1\)，

\(\begin{aligned} &ans=\sum\limits_{i=0}^{m-n} k^{m-n-i}(k-1)^{i}\dbinom{n+i-1}{n-1} \\ &=\sum\limits_{i=0}^{m-n}(x+1)^{m-n-i} x^{i}\dbinom{n+i-1}{n-1} \\ &=\sum\limits_{i=0}^{m-n} x^{i}\sum\limits_{j=0}^{m-n-i} x^{j}\dbinom{m-n-i}{j}\dbinom{n+i-1}{n-1} \end{aligned}\)

考虑枚举 \(i+j\) 的和 \(p\)。

\(ans=\sum\limits_{p=0}^{m-n} x^p \sum\limits_{i=0}^p \dbinom{m-n-i}{p-i}\dbinom{n+i-1}{n-1}\)

注意一下后面的 \(\sum\limits_{i=0}^p \dbinom{m-n-i}{p-i}\dbinom{n+i-1}{n-1}\)。

变形为 \(\sum\limits_{i=0}^p \dbinom{m-n-i}{m-n-p}\dbinom{n-1+i}{n-1}\)。

注意到这是组合数相乘的形式，而且变量都放在 \(\dbinom{a}{b}\) 中 \(a\) 的位置，考虑使用组合数恒等式。

进而 \(\sum\limits_{i=0}^p \dbinom{m-n-i}{m-n-p}\dbinom{n-1+i}{n-1}=\sum\limits_{i=1-n}^{m-n} \dbinom{m-n-i}{m-n-p}\dbinom{n-1+i}{n-1}\)

（此处扩充求和上下界是为了下一步可以套用组合数恒等式）

由组合数恒等式 \(\sum\limits_{i=-q}^{l} \dbinom{l-i}{n}\dbinom{q+i}{m}=\dbinom{l+q+1}{n+m+1}\) （见《具体数学》表 5-3，可通过上指标翻转和范德蒙德卷积式推出。）

我们 惊奇地 发现式子可以化为 \(ans=\sum\limits_{p=0}^{m-n} x^p \dbinom{m}{m-p}=ans=\sum\limits_{p=0}^{m-n} x^p \dbinom{m}{p}\)。

这类似一个二项式展开地形式，和 \((x+1)^m=\sum\limits_{p=0}^m x^p\dbinom{m}{p}\)唯一的区别是求和上界 \(m-n\)。

但是 \(\sum\limits_{p=m-n+1}^{m} x^p \dbinom{m}{p}\) 只有 \(O(n)\) 项，可以很好算出。于是拿 \((x+1)^m\) 减去 \(\sum\limits_{p=m-n+1}^{m} x^p \dbinom{m}{p}\) 即是答案。

（计算 \(\dbinom{m}{p}\) 可以直接把组合数计算式中的阶乘乘除相消后的项乘起来）。

带上快速幂的 \(\log\)，时间复杂度 \(O(n\log n)\)。

code

Submission #227816023 - Codeforces

P.S.

这个题更好的推导方法是推出 \(O(m)\) 的式子后发现答案与 \(a\) 的具体值无关，利用这个性质可以找到更利于解决问题的组合意义，比如：不妨令所有 \(a_i\) 的值都相同，则不合法的方案数就是 \(\sum\limits_{i=0}^{n-1} \dbinom{m}{i}(k-1)^{m-i}\)，与上文推导的结果一致。本文主要是阐述如何正面得出这个结论。