好不容易把省队集训的题重新写了一遍，当然是只写了自己比较会的题QAQ，所以来总结下写过的题的题解，如果哪里写错了请大佬指正QAQ，没写的题写完会补上
Day 1
这天的题有点毒瘤，先跳了
Day 2
T1
T2 仙人掌
首先我们知道只保留编号在([l,r])的点时，联通块数=点数-边数+环数
那么考虑枚举右端点，对于每个左端点用线段树维护答案
于是只需要考虑新加进来一个点的贡献：点数+1，和(r)相连的边到达的点如果比(r)小就算贡献，所有编号最大值是(r)的环也要算贡献
因为是仙人掌，所以我们可以用求圆方树来求出每个环的编号最小值和最大值
Day 3
T1 如何优雅的送分
(2^{F(i)})可以看作枚举(i)的质因子集合的子集，那么考虑直接枚举每个子集(d)，那么有(lfloorfrac{n}{d} floor)个子集包含它，所以原式变为了
这个式子就可以直接做了
T2 阴阳
看着就非常可持久化点分树，我的可持久化点分树写法是：对每个点开动态开点线段树，每次对在点分树上修改的(logn)棵线段树建立新版本，再用主席树维护每个点各个版本对应的信息
T3 你猜是不是找规律
题目的实质是问一个长度为(n)的排列，交换(k)次能得到多少本质不同的排列
考虑一个简单的dp，设(f[n][k])表示长度为(n)的排列交换了(k)次得到本质不同的排列个数，只考虑第(n)位，要么不参加交换，要么交换一次，那么转移方程有(f[n][k]=f[n][k-1]+f[n-1][k-1] imes(n-1))
(k)一定的时候(f[n][k])是个关于(n)的多项式，这个多想是的次数我们可以通过差分得到是(2k-1)次，最后答案求前缀和也就是(2k)次多项式，直接拉格朗日插值就可以了
Day 4
T1 树论
答案转化为所有距离(x)深度不超过(d)的边权和(*2-)该联通块的直径
那么我们考虑线段树合并，维护每个深度的联通块边权和和直径，然后有一个显然的结论，两个联通块的直径端点分别是(a,b,c,d)，那么合并后新的直径也一定是在这4个点之中
T2 图论
考虑对两种路线建不同的边
第一种路线建两棵以最大值为根的笛卡尔树，一棵由儿子向父亲连边，另一棵由父亲向儿子连边（边权均为0），然后对应点连这个点的点权的边，每次走的一定是两点的lca，也就是最大值
第二种路线建两排辅助点，大概是这样子（懒得画图了就只好搬原题解的图了QAQ）
这样最短路一定会走最短的那条边
T3 几何
凸多边形划分后原多边形的边一定在三角形上，三角形把这个凸多边形划分成了两部分，而这两部分的生成树的导出子图只有两种情况，要么是一棵树，要么是两棵树（因为在三角形上的边的端点只有两个）
那么我们可以根据这个进行dp，设(f[i][j])表示((i,j))这条边分割出来(i)到(j)这些点对应第一种情况的方案数，(g[i][j])就表示对应第二种情况的方案数。
然后找到三角形的另一个端点(x)，则有转移式
具体就是看看(i,j)这条边选不选，然后从(1,n)开始dp就可以了
而我们有用的状态只有(2n-3)个，如果枚举找(x)是(O(n^2))的，用set找就变成了(O(nlogn))
Day 5
T1 毒瘤约数
由2条件可得(D[i]|N)，对3条件做均值不等式可得出(D[i] mid D[j])
那么我们可以直接对(N)的约数建图跑最长反链
然后我们猜想最长反链一定是在多层图中的某一层，于是我们可以对(N)的质因子构造一个生成函数，直接算答案（为什么是对的我也不知道QAQ）
T2 毒瘤树
题目其实就是让你求直径在([l,r])的联通块个数
这个东西我们可以首先转化为前缀和的形式，于是我们只需要求直径小于等于(R)的联通块个数
那么考虑树上dp，设(f[u][d])表示(u)为最浅点，最深点距离(u)为(d)的联通块个数，那么有转移方程
然后考虑优化这个式子，那就把max拆开，则有方程
第一个式子可以用前缀和优化
而对于第二个式子，这个看起来像加上一个数的(x)倍，而注意到刚开始(f'[u][d1]=f[u][d1])，那也就是乘(x+1)倍
因此我们用线段树对第一个式子维护单点修改，第二个式子维护区间乘，然后记录每个数被乘了多少次可以用map维护
这样子复杂度是(O(n^2log(n)))
那么我们对其长链剖分，每次先dp深度最深的儿子，那么第一次只需要转移(f[u][d+1]=f[u][d])，而当按dfs序优先对长链标号后，这个就相当于区间平移，那么问题就游刃而解了
复杂度(O(nlog(n)))
T3 毒瘤题面
如果一个数(x)在长度为(n)的区间出现了(c)次，那么其对答案的贡献为(2^{n-c} imes(2^c-1)x=x(2^n-2^{n-c}))，具体就是不包含(x)的序列个数乘包含(x)的序列个数
那么我们可以用一个莫队来统计答案，而模数每次不同比较的棘手
可以注意到一个长度为(n)的序列本质不同的出现次数是不超过(sqrt{n})的，因为(1+2+3+...sqrt{n}=n)，那么我们用链表存下来，统计的时候暴力算就好了
快速幂的话还需要用光速幂
复杂度(O(nsqrt{q}+qsqrt{n}))
Day 6
T1 简单题
对题目简单化式子可以发现(1^K(R))的意义是选(K)个数乘积为(R)的方案数
我们注意到(K)是一个非常大的，而一个数被整除(log)次就变成(1)了，所以一定会有非常多的(1)，于是可以考虑去掉(1)的情况进行dp
设(f[n][k])表示选(k)个非(1)的数乘积是(n)的方案数，那么可以这么转移
(k)枚举到(log)就可以了，而通过刷表也就是类埃氏筛的做法可以将复杂度做到(O(nlog(n)loglog(n)))
然后剩下的(1)就非常的好办，只需要考虑把这些(1)看成物品，而方案就是把(k)个因数替换掉(1)的方案数，也就是(C_{K}^{K-k}=C_{K}^k)
那么最后的答案
(f)可以通过前缀和查询区间，(C_K^k)可以递推得出
T2 简单三角
一个三角形的简单值可以通过皮克定理求得，剩下的就是一个裸的三元环计数
先根据度数把边定向，枚举边，再一个端点，将端点到达的点标记，再枚举另一个端点到达的点，如果有标记就是一个三元环
复杂度(O(nsqrt{n}))
注意下要把点和边去重，不然复杂度是错的
Day 7
T1 a xor b problem
考虑如何把(a)进制转成(b)进制
那么回忆(a)进制转(10)进制的过程
在(b)进制下做这个式子就可以了
而这题有高精，那么考虑如何加速这个过程
左右两个和式可以递归做下去，中间的(a^{frac{n}{2}} imessum_{i=0}^{frac{n}{2}}x_{i+frac{n}{2}} imes a^i)可以用fft加速
时间复杂度(O(nlog^2(n)))
T3 猜数游戏
我们考虑(n=3,k=2)的时候怎么做
先猜两次(0)，如果全是否那么一定是真话
不然在第一次说是之后问一个(1)
如果回答是那么答案一定在(0,1)之中，所以一定不是(2)
如果回答否那么一定不是(1)
所以我们一定可以排除一个数字
而(n,k)变大之后怎么做
一样按上面的思路，先问(k)次(0)，全是否那么一定是真话，否则就在第一次回答是的时候进行询问
那么我们现在有(2^{k-1})个数，有(k-1)次询问，于是可以考虑二进制划分，每次询问编号有(2^i)的数，通过(k-1)次询问后可以唯一确定一个数