Description

难以描述,看图:
图片说明

Solution

简单的来说就是

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

方案统计

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

结论证明(摘自百度):

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

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

Code

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