【SDOI2014】数数


题意

求满足\(\le n\)且不包含集合\(S\)中任意字符串作为子串的个数。

分析

多子串问题,考虑在AC自动机上dp。

\(f[i][j][k]\)表示到数字的第\(i\)位,对应AC自动机上的第\(j\)位,是否有最高位的限制\(k=0/1\)。

直接通过AC自动机getfail以后的\(ch\)数组转移即可。

有一类特殊情况是字符集\(S\)包含前导\(0\),而数字中的前导\(0\)会被去掉,又一个方便的处理办法是手动把AC自动机中的\(ch[0][0]\)边删除。

 

You may also like

【TJOI2015】弦论

【AHOI2013】差异

LEAVE A COMMENT

Statistics

  • 0
  • 8,099

Categories

Archive

Comments