作者：党星宇

取石子游戏

Solution

由于本人水平极低，所以觉得此题难死了。 通过看题解不难发现，对于一段区间$[L,R]$，若$L+1$ 到$R$每堆石子个数确定，那么使得这段区间上先手必败的$a[l]$有且只有一个。 证明非常的容易。首先假设没有先手必败的$a[L]$，那么所有的必胜态都会到一个必胜态，显然是不可能的。如果有$\geq 2$个必败态，考虑其中任意两个$x,y,x>y$，那么先手显然可以把$x$取成$y$，那么$x$就是一个必胜态。矛盾。 于是，我们定义$left[i][j]$表示在$[L,R]$区间左边添多少个变成一个必败态，$right[i][j]$表示在右边添多少个。那么答案就是$left[2][n]!=a[1]$。现在考虑如何求$left[l][r]$。设$L=left[l][r-1],R=right[l][r-1],X=a[r]$我们可以分以下几种情况讨论。 继续阅读

An unavoidable detour for home

Solution

由最短路唯一，不难发现以下性质：

1、原图可以通过对于$1$号点的最短路长度分层，成一棵树的形式，每一层的最短路长度相同。

2、剩下的边只能在树的同层内的点加。

3、由于要求对于$i>j$有$dis_i>dis_j$，所以每一层是一段区间。

于是，我们就可以$DP$了。显然有一个暴力的做法，$f[i][pre_1][pre_2][now_1][now_2]$表示上一层剩下的度数为$1$的点有$pre_1$个，度数为$2$的点有$pre_2$个。这一层的对应分别有$now_1,now_2$个。转移讨论一下$i$号点的连边情况。当$pre_1=pre_2=0$时，这一层就填完了，该填到下一层。

显然是可以通过预处理同层里的方案数直接每层转移。注意到度数为$2$的点的方案数要提前除$2$。

同时注意到，数据范围只有$50$，所以好写$n^5$暴力就可以愉快通过了。真好写

小朋友与二叉树

Solution

对$C$这一维做一个生成函数，易得$C(x)=\sum_{i\in S}x^i$

然后我们在考虑二叉树，对于二叉树做一个生成函数$F(x)$。

我们不难发现
$$
F(x)=C(x)F^2(x)+1
$$
为什么是这样呢？我们考虑左右儿子合并在一起之后就是$F^2(x)$再加上根自己的贡献就是$F^2(x)C(x)$，然后我们发现常数项没有了，所以最后$+1$表示空树。

然后我们就可以愉快的解方程了，通过求根公式可以得到
$$
F(x)=\frac{1\pm\sqrt{1-4C(x)}}{2C(x)}
$$
其中有一个$\pm$该怎么办呢？通过简单观察我们可以发现，分母的常数项为$0$。如果是$+$，那么开根号后得到的多项式的常数项一定是一个非负数，所以这样分子就一定会有常数项，那么整个分数就一定会有余数。故上面只能为$-$。

于是我们就可以通过之前介绍过的多项式开根和多项式求逆元解决这道题了。

牛顿迭代法

对于一个已知的函数$G(x)$，我们要求一个多项式$F(z)\pmod {z^n}$，满足方程
$$
G(F(z))\equiv0\pmod{z^n}
$$
牛顿迭代法是一个倍增解决的过程。

继续阅读

本文将介绍一些关于多项式的基础内容并记录下笔者从零开始学习多项式的过程。

继续阅读

对于一个$k$次的多项式$F(x)$，已知$F(0),F(1),F(2),…,F(k)$，求出$F(n)$

这个问题可以在$O(k)$的时间复杂度内解决。下面将介绍具体做法。
继续阅读