作者：党星宇

两个关于Square Factor的趣题

党星宇 评论

本文讨论了两个关于square factor的趣题。

首先介绍一下square-free number（虽然和下面的内容没有什么关系）

我们称一个数是square-free的，当且仅当它没有平方因子（关于平方因子的定义在Part\ I中）

我们用S(n)表示1到n的square-free number的个数，有它的渐进式

\lim_{n\rightarrow \infty} S(n)=\frac{6}{\pi^2}n+O(\sqrt{n})

如果广义黎曼猜想成立，我们可以进一步减小误差：
S(n)=\frac{6}{\pi^2}n+O(n^{17/54+\epsilon})

继续阅读

BZOJ1413[ZJOI2009]取石子游戏

党星宇 评论

取石子游戏

题目链接

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]我们可以分以下几种情况讨论。

继续阅读

CF814E An unavoidable detour for home

党星宇 评论

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暴力就可以愉快通过了。真好写

BZOJ3625小朋友与二叉树

党星宇 评论

小朋友与二叉树

题目链接

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。如果是+，那么开根号后得到的多项式的常数项一定是一个非负数，所以这样分子就一定会有常数项，那么整个分数就一定会有余数。故上面只能为–。

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