csp-s模拟97

T1:
? 打表？？？
? （其实是手模……）
?
T2:
? 设计状态\(f_{i,c,0/1}\)表示考虑到第i位，已经有了c个相同的，之前是否已经有了三个连续的，的方案数
? 转移显然，不过可以矩阵快速幂优化，然后优化后的复杂度为O(6^3logn)

? 还有一个思路：
? 考虑有且仅有一个三个连续的，那么我们可以计算长度为i不出现三个连续的的方案数\(g_i\)
? 转移：\(g_i=(s-1)(g_{i-1}+g_{i-2})\)
? 最后答案即为：\(\sum _{i=0}^{n-3} g_ig_{n-i-3}(\frac{s-1}{s})^2s\)
? 这个g的递推也是可以矩阵快速幂优化的，但最后的ans似乎不太好优化(?)
?
T3:
? 正解是扫描线加线段树套set（好麻烦啊）
? 然而我们可以通过分析发现出题人不怎么毒瘤，所以应该不会卡一些奇奇怪怪的算法（？？？）
? 所以我们可以用kd-tree！（好写啊）
? 虽然时空复杂度都可以被卡到不对，但可以水过！