题解、Writeup、游记和碎碎念
包含标签 DP 的文章
给出一个长度为 N 由 B、W、X 三种字符组成的字符串 S，你需要把每一个 X 染成 B 或 W 中的一个。
对于给出的 K，问有多少种染色方式使得存在整数 a,b,c,d 使得:
1<=a<=b<c<=d<=N
Sa,Sa+1,...,Sb 均为 B
Sc,Sc+1,...,Sd 均为 W
其中 b=a+K-1,d=c+K-1
由于方法可能很多，因此只需要输出最后的答案对 109+7 取模的结果。
阿申准备报名参加 GT 考试，准考证号为 N 位数 X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。他的不吉利数学 A1A2...Am(0<=Ai<=9)有 M 位，不出现是指 X1X2...Xn 中没有恰好一段等于 A1A2...Am. A1 和 X1 可以为 0