Codecraft-18 and Codeforces Round #458 友情客串

TCO的神题真的做不动了
不如换换脑袋吧
### E Palindromes in a Tree
题意：给你一棵$N$个点的树，每一个点有一个字母$'a'-'t'$，对每个点回答有多少经过它的路径是回文的。一条路径回文当且仅当它的一个排列是回文的。$N\le 10^5$

题解：考虑直接上点分。每一层一棵一棵子树做，先预处理出$f_{mask}$表示以根开始的每条路径$mask$状态的字母的奇偶性。每一次更新$f_{mask}$表示除了终点落在当前子树内的$mask$状态的字母的奇偶性。考虑到只有全部是偶数或者一个是奇数其它是偶数才合法。那么我们到一个点就枚举哪个字母是奇数，异或出答案即可。并在当前点打差分标记。
最后把所有的差分标记上推，每一个点答案除以$2$。
复杂度：$O(20\times NlogN)$

### F Substrings in a String

题意：长度为$N$的字符串支持$m$个操作：
1、修改一个位置$i$为字符$c$
2、查询$s:[l,r]$内$t$出现的次数。
$N\le 10^5,\sum|t|\le 10^5$

题解：居然可以用$Bitset$……
对每一个字符建一个$Bitset$。
因为$T=\sum|t|\le 10^5$，每一位我们都去把对应的字符的$Bitset$移位当前匹配长度然后与一下，最后用count统计有多少$1$。
复杂度$O(N^2/64)$

实际上正解是分块。
如果长度大于$\sqrt T$发现这样的串最多$\sqrt T$个，暴力跑$kmp$，总复杂度$N\sqrt T$。
如果长度小于$\sqrt T$讨论如下：
1、不跨块，直接对每一个块建立$SAM$，然后在$\sqrt N$各$SAM$里跑就行了。
2、跨块，发现每一个分界的地方只需要讨论$2|T|$长度的串，直接使用$kmp$。复杂度$T\sqrt N$
修改的时候暴力重构$SAM$，复杂度$m\sqrt N$
对于左右散块查询同样使用$kmp$即可。
总复杂度$O(10^{\frac{15}{2}})$，优秀。

### G Sum the Fibonacci
题意：给一个数列$s$，求这样的东西：
$$\sum_{s_a\&s_b=0,(s_a|s_b)\&s_c\&(s_d\bigoplus s_e)=2^k}f(s_a|
s_b)\times f(s_c)\times f(s_d\bigoplus s_e)$$
其中$f(i)$是斐波那契数列$i$项。

题解：子集并卷积推广题目。网上有一篇很好的博客：[子集并卷积](http://blog.leanote.com/post/rockdu/0325)
使用$FMT$做子集并卷积完成$g(i)=s_a|s_b=i的对数且s_a\&s_b=0$的统计，把$g(i)$的每一项乘上$Fib_i$。
使用$FWT$做异或卷积完成$h(i)=s_a\bigoplus s_b=i的对数$的统计，把$h(i)$的每一项乘上$Fib_i$。
令$f(i)=[i\in s]Fib_i$
然后使用$FST$求出$g,h,f$与卷积，就可以计算答案了。
总复杂度瓶颈在于子集并卷积。

Rockdu's Blog

导航

最近发表

大佬们的友链