(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）

T1 走格子
模拟即可

T2 求值2
存在公式
C(2n, n)=ΣC(I,n)*C(I,n) (0<=i<=n)
预处理阶乘和逆元
即可O(n)出解

T3 简单环
状态压缩DP
考虑把环拆成一条路径
设f[s][i]表示当前路径中点的状态为ｓ，且当前路径的末尾为ｉ
为了使路径不重不漏
我们每次枚举一个编号最小的点ｖ作为起点
ｓ中的状态的其他点的编号必须比ｖ的编号大
时间复杂度O(n^2*2^n)

T4 01序列2
对于一个二进制串，考虑dp来记录有多少个子区间是3的倍数。
设f[i][j]表示当前在二进制串第i个位置，模3余数为0的方案数。
对于一个二进制串可以O（n）出解。
考虑一个对二进制数分治求解。
设s(l,r)为区间[l,r]的解，则
其中S(l,r)表示跨越mid的[l,r]的是3的倍数的子区间的数量。
设为区间[l,r]中右端点为r且模3余i的子区间的数量；
为区间[l,r]中左端点为l且模3余j，且2区间长度模3为i的区间的数量。
N[l,r]表示区间[l,r]表示的数。

建成动态分治结构即可在O（nlogn）的时间复杂度内通过此题。

T5 跳格子
从最后一个格子跳回第一个格子之前可以看作是从一个格子之前跳到最后一个格子
所以题意就变成了
跳两次
第二次跳必须踩在第一次跳的格子上
则第二次跳的格子的集合必定是作为第一次跳的格子的子集
我们考虑枚举枚举第二次跳的距离i
搜索有第一次跳的长度为i的方案数vi
然后有递推式f[n]=f[n-1]v1+f[n-2]v2+..+f[n-m]*vm
递推即可

T6 树的颜色
询问离线然后整体二分
二分答案
如果当前到了答案区间为[l,r]
设A数组为颜色在[l,r]之间的树点
设B数组为答案在[l,r]之间的询问
Mid=l+r>>1
对A数组种颜色编号在[l,Mid]之间的树点建一棵虚树T
对于每个B数组的询问
查询每个询问在T中对应的区域内有多少种颜色
如果小于K则递归到Mid]
如果大于K则K-=颜色种类数，递归到[mid+1,r]
现在问题变成了每次查询一棵子树内深度在小于等于y的点内有多少种颜色
我们把树点按深度排序
然后按深度为版本，按dfs序为下标建立***树
然后插入树点
每次加入一个颜色为i的树点
设pre为dfs序小于u的dfs序且dfs序最大的颜色为i的点
设suf为dfs序大于u的dfs序且dfs序最小的颜色为i的点
那么u的权值+1
Lca(pre,u)的权值-1
Lca(u,suf)的权值-1
Lca(pre,suf)的权值+1
这样每次询问在对应的深度版本上即可logn查询颜色种类
总时间复杂度(nlog2n)

其他疑问可加以下交流群（加入一个即可啦~）
牛客多校算法训练营1：453799454
牛客全国算法训练营2：330766563
牛客多校算法训练营3：934889305