Atcoder Grand Contest 020 E

题意：给一个\(0-1\)字符串，如果其中有一段重复，就可以表示成\((\)这一块的表示\(\times\)出现次数\()\)。

问这个字符串的所有子集中有多少种表示方法。

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

思路：考虑\(dp(s)\)表示字符串\(s\)的答案。

那么我们得考虑第一个表示成的位置是什么。

①第一位就是表示的第一位，不参与循环。那么转移到\(dp(s.substr(1))\)，并且如果这位是\(1\)，那么乘上\(2\)，因为这位可能是\(0\)。

②一个前缀是循环节。那么转移到这个循环节的答案乘上后面的那一段的答案。这个循环节是它循环的内容中所有段的\(and\)，即按位与。

然后记得取模就好了。

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄