【题解】牛客挑战赛35

T1:考虑用你手上最小的牌去碰对面最大的，次小的碰次大的……以此类推。
证明如下：
令你的初始总分为你手上的牌的点数和减去对面的点数和。每次当你的牌小于对面的牌时，你将获得的分数。不难发现这个问题与原问题等价。
现在假设在游戏过程中，你有次出牌小于对面的，显然为了最大化分数我们应该选你的最小张碰对面最大张。当不断增加时，若你的小牌小于对面的大牌，则你的分数会增加。模拟这个过程计算即可.

T2:对每个联通块分别考虑。如果这个联通块是一条链，则最后收缩至.如果是一个环，则点数不变。如果是一个拥有四个点的菊花图，答案是.其他情况均发散至正无穷。对每个联通块求和即可。

T3:令表示长度为i的置换的循环节个数总和，则，可以线性求出。
现在考虑钦定置换的前位和给定置换相同，第位比给定置换大，后面随意（显然字典序更大）。则我们考虑建立对应的有向图，一个循环节对应有向图中的一个环。已经成环的那些点可以直接计入答案。设未成环的链共条，则可以将每条链等效为一个点，并将计入答案。使用并查集维护该有向图，树状数组优化枚举位的值的过程即可。

T4:将串不断执行操作，直到串消失，所得到的一系列串构成的集合记作。将中的每个串逐位翻转（不删去前导零）后构成的集合记作。则是好的串，当且仅当可以通过和中的串拼接而成。使用DP判断即可。

T5：真实良心送分题。将所有需要用到的（为添加的边的端点或者所求最短路起始/终止点）拉出来建虚树构图，最后跑最短路计算答案(std写的spfa哈哈哈哈哈哈）。

T6:令为一个多项式，的值表示当取值为x时，满足前面所有限制的概率。可以证明是一个段数在级别的分段多项式（通过维护可证）。最后答案就是
我们可以得到。转移的时候枚举的所有段进行计算。