讨论 - 求01字串思路

Wych 2009-10-11 07:43:00

点我顶贴收藏删除

那位牛有公式和证明？

#1 Wych@2009-05-09 00:29:00

回复删除

求解中

#2 blacksnow@2009-05-09 01:10:00

回复删除

这道题目不是可以暴搜么？

将一部分（01字串的长度《=n Div 3）01字串转化为10进制，并且不可能连续出现三个相同字串..题目的范围才40...应该可以过...

#3 Wych@2009-05-09 07:57:00

回复删除

暴搜？？？

2^40是不是太大超时,好像并不高效.

没有什么经典的数论解法吗...

#4 lc123456@2009-05-15 02:36:00

回复删除

打表

#5 lc123456@2009-05-15 02:37:00

回复删除

打表

#6 xxwzy@2009-05-15 05:09:00

回复删除

bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！bs打表！

#7 curimit@2009-05-16 00:20:00

回复删除

我用AC自动机A掉了。

由于长度是40，40/3=13

我们先可以把所有禁止出现的子串搜出来，最多有16000多个。

然后我们建一个AC自动机。

预处理出go[i,0]和go[i,1]表示在自动机第i个节点后键入0或1，转移到的自动机的节点编号。

如果go[i,0]或go[i,1]恰好是某个禁止子串的结尾，那么就令go[i,0]或go[i,1]等于-1

方程:

设f[n,i]表示长度为n，并且当前状态在自动机第i个节点时的方案数。

用f[n,i]的值更新f[n+1,go[i,0]]和f[n+1,go[i,1]]的值。

最后输出sigema{f[n,i]}(1<=i<=自动机节点数)

#8 天￠殇@2009-05-16 00:35:00

回复删除

纯搜索能过..

#9 curimit@2009-05-16 01:04:00

回复删除

纯搜索咋过？

#10 xxwzy@2009-05-16 01:34:00

回复删除

7楼大牛