TJOI2019

TJOI出一堆模板题还玩一堆梗是什么鬼

甲苯先生的字符串（矩阵快速幂）

矩阵快速幂模板题

代码

甲苯先生的滚榜（树状数组、线段树）

最开始想平衡树搞，但是~~平衡树太难写了~~

一次答案的查询相当于查询比当前的人AC数多的人数+和当前的人AC数一样多，但是罚时更少的人。前者可以使用树状数组维护每一种AC数量的人数的前缀和，后者使用动态开点线段树，在修改的时候可以一并求出答案。

注意动态开点线段树及时回收无用空间，空间消耗就很少了。

如果不知道怎么开数组就统统开\(5 \times 10^6\)……

代码

唱、跳、rap 和篮球（容斥、生成函数）

~~律师函警告~~

其实这道题也挺板子的，但是容斥没学好有点不会qwq

注意到两个不合法序列之间不可能相交，所以可以容斥序列中总共出现了多少个不合法序列，然后计算本质不同的排列的方案数。由指数型生成函数，有\(i\)个不合法序列的序列的贡献是\(n![x^n]\frac{x^{4i}}{i!}(\sum\limits_{j=0}^{a-i} \frac{x^j}{j!})(\sum\limits_{j=0}^{b-i} \frac{x^j}{j!})(\sum\limits_{j=0}^{c-i} \frac{x^j}{j!})(\sum\limits_{j=0}^{d-i} \frac{x^j}{j!})\)。

直接NTT复杂度\(O(n^2logn)\)可以通过，但有复杂度更优的做法：枚举\(i\)时维护\((\sum\limits_{j=0}^{a-i} \frac{x^j}{j!})(\sum\limits_{j=0}^{b-i} \frac{x^j}{j!})\)和\((\sum\limits_{j=0}^{c-i} \frac{x^j}{j!})(\sum\limits_{j=0}^{d-i} \frac{x^j}{j!})\)，因为\(i\)每次增大\(1\)，这四个式子只会少一项，所以可以\(O(n)\)更新，求出这两个多项式的卷积的其中一项也可以\(O(n)\)。这样复杂度变为\(O(n^2)\)。

代码

大中锋的游乐场（最短路）

分层图最短路模板题

代码

甲苯先生和大中锋的字符串（SAM）

SAM求endpos模板题

代码

甲苯先生的线段树（记忆化搜索）

~~谢罪警告、328警告~~

原题：CF750G ~~禁赛3年警告~~

应该是TJOI里面最妙的题目了。第一问暴力跳父亲。在下面的叙述中，设第一问的答案为\(len\)。

对于第二问，考虑枚举链上深度最低的点\(x\)、\(x\)的左儿子和右儿子的链深度\(L,R\)（\(L,R\)可以为\(0\)），记作三元组\((x,L,R)\)，那么这条链的编号总和的下界是\(x+2x+...+2^Lx+(2x+1)+(4x+2)+...+(2^Rx+2^{R-1}) = (2^{L+1}+2^{R+1}-3)x+2^R-1\)，也就是两条链都向左延伸的情况。

对于长度为\(L\)的左链，自底向上，第\(1,2,...,L-1\)个点都可以选择其父亲的左儿子或者右儿子，对于第\(i\)个点，选择右儿子相比选择左儿子编号之和会增加\(\sum\limits_{j=0}^{i-1} 2^j = 2^i-1\)，右链同理。那么不难得到整条链的编号和上界是\((2^{L+1}+2^{R+1}-3)x+2^R-1+2^L+2^R-L-R-2\)，即两条链都向右延伸。因为\(2^L+2^R-L-R-2 < 2^{L+1}+2^{R+1}-3\)，所以\((x,L,R)\)的链编号和上界比\((x+1,L,R)\)的下界还要小，说明每一个\(x\)对应的链编号和范围无交。

那么不难得到枚举了\(L,R\)之后，\(x\)只有可能等于\(\lfloor \frac{len - 2^R+1}{2^{L+1}+2^{R+1}-3} \rfloor\)。接下来我们的任务是给左链和右链的节点分配是其父亲的左儿子还是右儿子。上面提到了第\(i\)个点选择右儿子相比选择左儿子会有\(2^i-1\)的增加量，所以我们需要求出一个长度为\(L-1\)的\(01\)串和长度为\(R-1\)的\(01\)串，\(01\)串的第\(i\)位为\(1\)有\(2^i-1\)的贡献，要求两个串的贡献和等于\(len - ((2^{L+1}+2^{R+1}-3)x+2^R-1)\)。这个可以数位DP，如果懒可以大力记忆化搜索。

至于记搜复杂度~~反正比数位DP的\(O(d^5)\)快很多就完事了证是不可能会证的~~

代码

巴特西