基础组合数学练习题（CF1747E）

· · 题解

本来不想写的。

考虑差分，我们不算最开始那一项，发现 a_i 和 b_i 不能 同时为 0。

枚举长度 k，考虑有几位不为 1， 根据插板法能得到 {n-1\choose l-1}，m-1\choose r-1。

然后你发现剩下的 B = 0，必须要在 A \not ={0} 上。

就是

\sum\limits_{k=1}(k+1) \sum\limits_{i=1}^{k} {n-1\choose i-1} {k\choose i}\sum\limits_{j=1}^k {m-1\choose r-1} {i\choose k-j}

我们知道范德蒙德卷积 \sum\limits_{k} {r\choose k}{s\choose n-k} = {r+s\choose n}

\sum\limits_{k=1}(k+1) \sum\limits_{i=1}^{k} {n-1\choose i-1} {k\choose i}\sum\limits_{j=1}^k {m+i-1\choose k-1} +i-1\choose k-1}

我们知道 {r \choose k}= \frac{r}{k}{r-1 \choose k-1}

右边的减 1 可以去掉。

直接可以得到 \frac{1}{n} \sum\limits_{k=1} k(k+1) \sum\limits_{i=1}^k {n\choose i}{k \choose i}{m+i \choose k} \frac{i}{m+i}

我们知道 {m\choose k}{r \choose m}= {r \choose k}{r-k \choose m-k}

所以 \frac{1}{n} \sum\limits_{k=1} k(k+1) \sum\limits_{i=1}^k {n\choose i}{m+i\choose i}{m \choose k-i} \frac{i}{m+i}

我们还要用 {r \choose k}= \frac{r}{k}{r-1 \choose k-1}

然后 \frac{1}{n} \sum\limits_{k=1} k(k+1) \sum\limits_{i=1}^k {n\choose i}{m+i -1\choose i-1}{m \choose k-i}

注意到后面的显然是关于 i 的项更多，所以换一下。

\frac{1}{n} \sum\limits_{i=1} {n\choose i}{m+i -1\choose i-1} \sum\limits_{k=i} k(k+1) {m \choose k-i}

有一个常见的技巧，我们注意到当且仅当 0 \leq k-i \leq m 才有意义，把上界替换掉。

\frac{1}{n} \sum\limits_{i=1} {n\choose i}{m+i -1\choose i-1} \sum\limits_{k=i}^{m+i} k(k+1) {m \choose k-i}

不妨令 k=k-i，这个应该很自然。

\frac{1}{n} \sum\limits_{i=1} {n\choose i}{m+i -1\choose i-1} \sum\limits_{k=0}^{m} (k+i)(k+i+1) {m \choose i}

我们不妨拆开 \sum\limits_{k=0}^{m} (k+i)(k+i+1) {m \choose k}

可以的得到 \left(\sum\limits_{k=0}^m k^2 {m \choose k} \right) + \left((2i+1)\sum\limits_{k=0}^m k {m \choose k}\right) + (i^2+i) \left(\sum\limits_{k=0}^m {m \choose k}\right)

中间是经典恒等式，直接写下来就是 m(m+1)2^{m-2} + (2i+1) m 2^{m-1} + (i^2+i) 2^m

回带回去得到 \frac{1}{n} \sum\limits_{i=1} {n\choose i}{m+i -1\choose i-1} (m(m+1)2^{m-2} + (2i+1) m 2^{m-1} + (i^2+i) 2^m)

然后就做完了！！！预处理 2^m 可以做到单次询问线性。

submission