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

Description

难以描述，看图：

Solution

简单的来说就是

• 在 区间里找一个公共子序列
• 在 这个点
• 后面的可以任意取。

方案统计

对于公共子序列部分，显然对于公共子序列可以做一次 统计方案数, 令 表示 串遍历到 ， 串遍历到 时有多少个公共子序列，类似于最长公共子序列那样去做就行了。
对于后面部分可以 任意取，假设当前 串剩下 个字母可以取， 串剩下 个字母可以取，显然方案数是 。
对于上式(1)有结论

结论证明(摘自百度)：

等式右边等价于：从 个不同的球中任意取出 个球，一共有的方法数。
等式左边 等价于：把个不同的球分成两块，从 个球中选出 个球来，从 个球中选出 个球来，由于从 两块中取的球数总是 个，每种方法加起来一定等于从 个球中取 个球的方法数。

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

Code

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