P11270 【MX-S5-T4】魔法少女们 题解

· · 题解

写+调了一晚上，写了 6k，破防了。

显然转成算每一对串的贡献，考虑暴力怎么做。

记一个串的和为其中左括号减右括号数，对于 T 而言是反着的。

第一种情况是相交，这个哈希判一下相交部分是否相等，然后还要算一下和是否为 0。

第二种情况就是不交，发现就是个简单格路计数，反射容斥一下即可。

这样就有 56 分了。

优化其实也不难。

第一种情况可以枚举相交长度和对应的一个串，把另一个串哈希值，长度，和放 map 里面即可。

第二种情况可以根据串的长度、和划分成若干等价类。

这样就有 84 分了。

但是感觉最后的优化还挺抽象。

注意到，由于格路计数写出来是两个组合数的差，由于 \binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m} 发现两个部分可以拆成 (x+1,y-1),(x+1,y+1)，(x,y) 表示之前的坐标（串长和和）。于是考虑把串长 \leq \sqrt L 的部分全推到一条直线上。复杂度就对了。

但是好像还过不了，换成平板电视就过了。

但是代码写起来就是一坨。