终于已经到了没有力气在意结果的时候了.

T1

原题, 模糊匹配就把模糊范围都标1, 一个串反序一下, 方便做卷积, 去检查贡献到的位置的结果是不是对的, 是就增加答案.

T2

神题. 我甚至还从未写过XOR最小生成树, 先把这个写了.

依然考虑分治, 把$8$以下的链接方法打表? 16以下的生成树打表? 然后就抄过不会了.

T3

原题. 考虑一个从右上到左下的路径, 至少有$\max(n,m)$是和答案一致的, 就考虑当路径穿过$y=x$时, 总是$\frac{1}{2}$的概率猜对, 所以我们统计直线上每个位置有多少条路径经过, 求和, 除以总的路径数, 就得到了经过每个位置的概率和, 再乘上$0.5$的期望贡献, 加上$\max$的贡献就是答案.