序列自动机
题目
链接：https://ac.nowcoder.com/acm/contest/4853/C
有一款自走棋有26种操作,每种操作我们都用a,b,c,d,...,x,y,za,b,c,d,...,x,y,za,b,c,d,...,x,y,z的符号来代替.
现在牛牛有一个长度为nnn的操作序列,他现在可以从里面拿出某些操作来组合成一个操作视频, 比如说操作序列是abcdabcdabcd,那么操作视频就有a,b,c,d,ab,ac,ada,b,c,d,ab,ac,ada,b,c,d,ab,ac,ad等(也就是操作序列的子序列).他现在想知道长度为kkk且本质不同的操作视频有多少种.
比如对于abababababab，长度为222且本质不同的结果有ab,aa,ba,bbab,aa,ba,bbab,aa,ba,bb。
考虑到答案可能非常大,你只需要输出在模1e9+71e9+71e9+7意义下的答案就可以了.
分析
首先把这个题目分解,分解就是一个1.n长度的数列选k个+2.(不重复)
第一个子问题就是Cn k对吧?用dp表示呢?
首先我定义dp,dp[i][j],i j表示在我选第i个的时候在j的范围的方案数
那么是不是 在我选第i个的时候在j的范围=在我第i个的时候j-1的范围(就是单纯的保存下前面记录的答案而已)+在我第i-1个的时候在j-1的范围（记录上个状态选的j-1的个数啊）;所以方程就是这个dp[i][j]=(dp[i][j-1]+dp[i-1][j-1])；
考虑不重复我们就可以思考重复怎么来的了?是不是我在第i个的时候选了这个字母下次还是选了这个字母这样就来了,这个问题怎么解决呢?第一种解决方案就是从后面选择最后一个这样既记录了所有答案又不会重复,但是这种请大家自己思考...我介绍一种简单的解决方法,这次我选了这个字母对吧,下次我选这个字母的时候-这次选这个字母的方案数是不是就是我现在的方案数了呢?肯定是的啊!dp[i][j]=(dp[i][j-1]+dp[i-1][j-1]-dp[i-1][l-1]);方程就是这个;最后注意下做减法时候的取模~
