2021牛客暑期多校训练营5 D.Double Strings (dp,组合数学)

Description

难以描述，看图：
图片说明

Solution

简单的来说就是

在 $[1,i - 1]$ 区间里找一个公共子序列
在 $i$ 这个点 $A[i] < B[i]$
$i$ 后面的可以任意取。

方案统计

对于公共子序列部分，显然对于公共子序列可以做一次 $dp$ 统计方案数, 令 $dp[i][j]$ 表示 $A$ 串遍历到 $i$ ， $B$ 串遍历到 $j$ 时有多少个公共子序列，类似于最长公共子序列那样去做就行了。
对于后面部分可以 任意取，假设当前 $A$ 串剩下 $n$ 个字母可以取， $B$ 串剩下 $m$ 个字母可以取，显然方案数是 $C_n^0 \cdot C_m^0 + C_n^1 \cdot C_m^1 + ..... C_n^m \cdot C_m^m(m\leq n)（1）$ 。
对于上式(1)有结论 $C_n^0 \cdot C_m^0 + C_n^1 \cdot C_m^1 + ..... C_n^m \cdot C_m^m(m\leq n) = C_{n + m}^{m}$

结论证明(摘自百度)：

等式右边等价于：从 $m+n$ 个不同的球中任意取出 $m$ 个球，一共有的方法数。
等式左边 $C_n^0 \cdot C_m^0 + C_n^1 \cdot C_m^1 + ..... C_n^m \cdot C_m^m = C_n^0 \cdot C_m^m + C_n^1 \cdot C_m^{m - 1} + ..... C_n^m \cdot C_m^0$ 等价于：把 $m + n$ 个不同的球分成 $m,n$ 两块，从 $m$ 个球中选出 $k$ 个球来 $[k=0,1,2,3,......,(m-1),m]$ ，从 $n$ 个球中选出 $(m-k)$ 个球来，由于从 $m,n$ 两块中取的球数总是 $m$ 个，每种方法加起来一定等于从 $(m+n)$ 个球中取 $m$ 个球的方法数。

于是考虑枚举 $A,B$ 中的两个端点，对于前后的方案数做乘法就可以了，比赛的时候想打 $C_n^m$ 的表 $1 \leq n \leq 10^4, 1 \leq m \leq 5000$ ，发现超内存了，索性打到 $n = 9500$ ，超出范围的卢卡斯暴力算，卡过去了（1950ms,250MB），~~正确的做法应该是先预处理出逆元~~?

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48362485