作为一套NOIP2008的卷子AK表示亚历山大。

1.统计N!末尾0的个数。正整数N<10^1000

2.要求支持三个操作：插入给定的字母串。删除给定的字母串。查询给定的仅含?与字母的正则表达式能匹配上的串数。操作数Q<3000，字符串长度<=20

3.给定N*M的01矩阵，每次操作可以让一个点和其八连通区域（如存在）的值1变00变1，最少几次操作让图上全是0。10组数据，N<=8，M<=8

4.给定N个长度相等且仅含?与字母的正则表达式。求恰能匹配其中K个表达式的字母串的个数对p的模。N<=15，长度<=50

表示前两题送分题后两题裸题。

我的傻叉题解：

1.高精除以单精，高精加。

2.暴力Q^2L乱搞。

3.标程是这样的：枚举第一行第一列，然后可以推出剩余的。比如第二行第二列，由于枚举了第一行与第一列，那么能影响第一行第一列的那个点的状态的只有第二行第二列这个点了。依次类推，所有点都被决定。复杂度是O(NM*2^(N+M))

但我用了另外一种方法……虽然也AC了但是我不知道有没有数据可以卡掉它，复杂度是O((N*M)^3)。

没错……就是异或方程组高斯消元……对于每个点可以列出一个方程……无解的情况就是0x=1的情况，而如果遇到0x=0的情况则默认x为0（反正按不按没关系就懒得按了），最后统计sigma(x)。

4.一开始没看到长度相等然后囧了。我的方法和标程一样，状压DP。f[i][j]表示前i位能恰好匹配状态j的个数。但是暴力是O(anl*2^n)的（状态是O(l*2^n)，转移要枚举下一位O(a)，然后将j中不能匹配上的那些点删掉O(n)）。实测很慢。7S出解。

那么观察哪些东西被重复计算了。一个就是每次都要看j中哪些点不能匹配。我们可以用s[i][j]存第i个字母为j的有哪一些。那么可以将O(n)变成O(1)：直接j&s[i][k]就可以了。

这样虽然能A题了，但是几乎是卡时过得。还能不能优化呢？当状态j中选中的个数少于k个的时候就可以剪枝。可以开两个数组存下>=K和=K的所有状态。这样全部20个数据可以在1.5s内出解。

但是Fotile神犇(Orz)的方法不怎么剪枝就可以0.5s内出解……如果不要求恰好，只要求可行的话就很好做了，那么要求恰好的话就要减去K+1个的（这一点我考试的时候没想到，K+1个的可行解中必定包含了所有K个的且都是重复计算的），再加上K+2个的……这样复杂度是一样的O(al*2^n)（吧？），但是预处理C(X,X)后常数会小很多。

• inline
• block