T0

WELCOME TO 传奇演出(CQYC) DP CONTEST.
不过有一道送分题，终于不用担心爆0了。
（题号按难度排序）

T1

容易知道，越后面进行平均操作的数字，最后在结果中的“权重”越大。
因此可以类似合并果子去做，每次取前两小的进行平均，这样得到的结果肯定是最大的。
注：因为前两小的数进行平均后肯定还是最小的，故可以直接排序去做。
当然两者的复杂度皆为O(n log n)

T2

根据暴力算法，我们知道，n为奇数时，答案是显然的n!
而对于偶数，要换一个思路。
由于正着去想并不是很容易，因此，我们容斥一下。
然后，对环进行染色，最开始每一个点都为白，随后任意选择一个白点，交换旁边的两点。
然后发现黑点无论怎样均无法变白，以这些黑点为端点，将环拆开。
我们发现点个数为偶数的链无解（再次分解仅能分解成偶数个数的链+奇数个数的链），对奇数段DP。
设f_n为长为2n-1的全0段变为全1段方案数。
$f_n=∑(i=1,i<n)C(2n-2,2i-1)fi*f(n-i)$