连续两天跪在T2上
A.水题不多说。和POI的某道sta十分相似。
C.考场上颓了2h+这道题，人弱不能多说。。。
我一开始想的是容斥。后来发现容斥的每一步也会重复。然后想了想我列的式子的意义，至少为k的数目。那get（k）-get（k+1）不就是答案了吗？
（说实话这种求某个特定值的真不容易想到用前缀和的差来求，反而如果要求k属于某个区间的话还容易想到用前缀和来解决）
我们用f[i]表示前i个中包含至少k个连续相同的方案数。那么我们可以枚举这一段的起点，得到递推式：
f[i]=sigma((power(m,j)-f[j])*(m-1)*power(m,i-j-k)) 1<=j<=i-k
含义其实是前面j个不能含有至少k个连续相同，所以就用总方案减去合法方案。然后第j+1个必须和j个不一样（否则起点就不是j+1了）然后j+1到j+k必须是m-1中颜色中的某一个，最后剩下的随便。
这样直接递推的话是O（n^2）的。但是我们考虑优化：
优化递推式我所知道的一般有两种：
1）观察是否是某两个其他式子的卷积，然后用FFT加速。如果求f[n]需要知道f[i]，那么我们可以用分治FFT。
2）观察f[i]和f[i-1]的差别，从而得出线性的递推。
这题显然不能FFT，然后f[i]和f[i-1]我们发现其实有f[i]=f[i-1]*m+（power(m,i-x)-f[i-x]）。
这样就做到O（n）了。
赛后发现其实转化成前缀和（我上面的做法是后缀和）好像思考难度更低，如果考场上能转化一下思路的话说不定能少走许多弯路。
B.我花了一个星期来学习做这题所需要的预备知识。。。
首先是博弈论，原来根本不懂什么博弈论QAQ所以考场上认为这题太不可做了，情况太多了。（其实看到sigma（k）<=100W我想到了虚树，真是naive）
然后补了下sg函数之后发现每个石子都是独立的游戏，然后我们只要预处理出每个点的sg函数值根据sg定理（然而我并不会证sg定理）异或起来判断是不是0就可以了。叶子节点的sg函数值是0，然后其他的节点的sg函数值为他能到达的后继状态的mex。
那这样其实我们就把问题转化成了求每个节点向下走不超过k步到达集合的sg函数的mex。。。
这样想其实就复杂了。我们考虑差分（多想一想也许就能想到差分？）
一个点sg函数计算完毕的时候将他加入自己的集合，然后把它从它的k+1级祖先的集合删去。每个元素的集合就是被删掉的加上儿子的集合（当然这里是可重集合）。
那么维护mex和单点修改其实线段树是可做的。但是现在有一个线段树合并的问题。
我们考虑两种方法：
1）启发式合并。
每次把两颗线段树中有效点比较少的拆出来一个一个加入到大的那棵线段树里面去。
我们考虑一下这样的复杂度，每个点所属的集合每次合并之后大小都会变为原来的至少2倍，所以这个点不会被合并超过logn次。
所以复杂度是O（nlog^2n）
2）线段树合并
代码看起来很简单也很熟悉的样子。
inline int merge(int x,int y,int l,int r)
{
if(!x||!y)return x+y;
if(l==r){update(x,t[y].sum,l);return x;}
t[x].l=merge(t[x].l,t[y].l,l,mid);
t[x].r=merge(t[x].r,t[y].r,mid+1,r);
pushup(x);
return x;
}
其实我原来并不知道这叫线段树合并，也不知道这个复杂度是如何证明的。
现在我们来证明一下：
首先，两棵线段树合并的复杂度是O（这两棵线段树的公共节点数）的。
评论 (0)
