「考试」省选39

非常值得反思的一场考试
考完改了20分钟就(AK)了。。。
(T2)的预处理处理到了(n-2)???
处理到(n-1)就(A)了。
(T3)的一个循环写错了位置，往下调了一格就(A)了。？？？
自闭场。
明天就(noi online)了。。
诶。。状态什么时候能来啊。
行吧,就这样吧。

T1
讲过。
将(a_i,b_i)连边。
将会形成环和链，统计一下环的个数。
然后链分为三种。
缩掉中间的那些非0部分可以分成：
(0 ightarrow 0)
(0 ightarrow x)
(x ightarrow 0)
设分别有(A,B,C)个。
然后枚举一下第二种的个数。
看他们单独组成的环有多少个：

[f(i)=sumlimits_{j=i}^{B}egin{bmatrix}i\jend{bmatrix}inom{B}{j}frac{(A+B-j-1)!}{(A-1)!} ]

为什么要-1呢？
意思是说我把这个位置以后作为划分的部分全作为这个(0 ightarrow 0)的附属品。
然后这样相同的板子一共有(A-1)个。
放进去一起排列。
然而这些板子是一样的。
所以除掉了((A-1)!)
相当于元素各不相同的插板。
然后设第三种单独成环的贡献为(g(i))
所以：

[g(i)=sumlimits_{j=i}^{C}egin{bmatrix}i\jend{bmatrix}inom{C}{j}frac{(A+C-j-1)!}{(A-1)!} ]

最后是(0 ightarrow 0)的贡献了。

[h(i)=A!egin{bmatrix}i\Aend{bmatrix} ]

因为这(A)个物品的取值是不一样的。
然后把他们全都卷到一起就可以了。
复杂度(O(n^2))。

T2
其实挺简单的。
就是一个容斥。
首先发现三条边均不存在的条件不是很好满足。
然后可以搞一个容斥。
答案就是：
无限制贡献-至少有一条边的贡献+至少有两条边的贡献-至少有三条边的贡献。
第一个直接枚举每个位置不限制然后线性计算即可(O(n))
第二个枚举边然后计算(O(m))
第三个枚举中间点然后枚举出边计算(O(m))
第四个三元环计数(O(msqrt{m}))
这样就可以出答案了。

T3
一个(exsam)。
比较难写不好调。
然后思路上挺简单的。
把(substring)那个题复杂化一点就行了。
建一个(exsam)就可以解决第一个和第三个问题。
第二个和第四个可以用(LCT)维护(parent)树，每个节点维护一下对于不同串的(endpos)集合大小就可以。
具体来说。
第二个操作就找到当时的那个前缀节点。
然后查询在当前(parent)树上当前然后查询一下某一个串的(endpos)集合大小。
第四个操作就直接在树上跑，然后最后跑到某个节点，把上面每个串的(endpos)集合大小取一个(max)即可。