拖更一年的模板题又更新辣！

拖更一年的模板题又更新辣！

拖更一年的模板题又更新辣！

欢迎大家来切，也欢迎更多新模板题/kel

你也许已经注意到，最近 nflsoj 出现了一道新的模板题：多项式复合逆。如果你不知道这是啥没关系，你只要知道这是杨主力 @fizzydavid 的题就行啦！

杨主力拥有 $10$ 个模板题位置，现在已经在路上或确定好的 idea 有下面几个：（立个flag不会鸽）

Lyndon分解，周期串拆分，回文串拆分，Trie上回文树，基本子串字典(Internal Pattern Matching)，多项式复合逆

如果你有什么好的模板题，欢迎在这篇博客下评论或者私戳，可以占这 $10$ 个坑，也可以问OJ管理员 @TRCYX 和 @diamond_duke 要空题（既然要了就自己造吧）。占了空题位之后，造数据和写题面的过程可以找几个人一起分锅，标程最好能自己提供。

为了鼓励大家踊跃造题，每贡献一个被认可的idea并出成题目，将获得多项式板子一个。

当然，模板题有一些要求：

1. 要符合模板题的身份。
2. 常见oj（ loj，uoj，洛谷等）上找不到相同的纯模板题，或者对应题目数据范围太小或数据太弱被大部分人用非 std 做法爆过去。（当然如果管理员滋磁且你有数据或愿意自己造可以忽略这条）

不过，如果你希望占杨主力的 $10$ 个坑（并强行让他帮你一起造这个题），请仔细考虑/xyx。

典型事例

A：最近刚刚学了个 *** 算法，能不能加到模板题里去啊/kel。

fizzydavid：不行，太简单了，出出来没有牌面。（说罢丢给你一篇论文）你看你/论文里的做法只能做到 $1000000$ ，我来给你加 $6$ 个零。

棋赢

是不是很像个多项式题呢？

令果子总数为sum，最终答案显然是 $\binom{sum-1}{n-1}$ 。由于n很小，前者可以暴力展开成一个关于sum的n-1次多项式。这意味着如果我们算出向量 $V=(\sum sum^0 ,\sum sum^1 , \sum sum^2 ,\dots ,\sum sum^{n-1})$ ，就可以求得答案。

定义 $f(V,x)$ 表示对V所代表的的当前答案中所有需要统计的sum值变成sum+x会怎么样。利用二项式定理可以把 $(sum+x)^k$ 展开，最终写成一个下三角矩阵 $M_{ij}=\binom i j\cdot x^{i-j}$ 。容易得到 $f(V,x)= M\cdot V$ 。

接下来考虑一只动物的影响，相当于把x=1到x=b所对应的的矩阵相加，也就是 $M'_{ij}=\binom i j\sum_{x=1}^bx^{i-j}$ 。得到这个之后，可以使用矩阵快速幂得到最终的答案。不考虑计算M的时间，总的复杂度是 $O(mn^3\log S_a)$ 。

至于转移矩阵显然是一个自然数幂和的形式，有多种方法优化。

某黑红出题人要求我把这题出成一个彻头彻尾的多项式题，数据范围变成$10^5$，然而本出题人非常良心没有同意。这部分就当做bonus啦！

std（上面blog没有描述，用了第二类斯特林数和下降幂的性质）在这里

或负

甩锅啦！原题戳这里，题解戳这里

std在这里

必去之

为了方便，把p改变，使得最优答案一定包含第一个和最后一个数，详见std。

定义f(i)表示考虑前i个数，且必须选择第i个时的LIS。那么有下面的公式，可以证明这样一定不会丢失最优解。 $$f(i)=\max\{f(j)+1+\min\{j到i之间的空格个数，p_j到p_i之间未出现在原排列的数的个数\}\mid j< i,p_j>0,p_j< p_i\}$$

可以发现min里面的两项都是部分和的形式，可以用前缀和改写。公式自行脑补然后把min操作分成两部分加到max的条件里面去，这样所求的max值为一个三维的RMQ。首先按i从小到大可以去掉一维，剩下的随便写个二维数据结构即可，复杂度2个log。

std（cdq分治）在这里

后记

实际上我写了一个很详细的题解，包括多种算法和部分分。然后在最后写好保存的时候网络模糊，最终保存到oj上的变成了一堆乱码...

不过出题人还是很良心艰难地把正解做法告诉了你们！至于具体公式和细节就留给你们脑补啦！

杨主力：写题解还带std的都是sb出题人！