本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-10-16 15:23:27

题外话

总结成绩：寄了。

T1-sbt

直接按照题意模拟，通过观察可以发现，向左走，变小，向右走，变大。
其实就是一个 BST。

T2-gift

实际不需要知道每个颜色出现多少次，只需要知道有多少个元素出现奇数次，有多少个出现偶数次。
设 $f_{i,j}$ 为前 $i$ 个有 $j$ 个颜色出现奇数次的方案数。
转移的时候，想一下下一个颜色是什么。如果下一个颜色在这 $j$ 个现在出现奇数次的颜色里面出现过，那么下一个状态出现奇数次的颜色数相较于现在减一。 否则下一个出现奇数次的颜色书相较于现在加一。

转移：f[i+1][j-1]+=f[i][j]*j，f[i+1][j+1]+=f[i][j]*(m-j)

代码在写。