题目要求恰好等于 M 的方案数,我们只需要求出小于等于 M 的和小于等于 M-1 的,相减即可。

考虑 Purfer 序列,他的长度为 N - 2,按照题目要求,每个数只能出现 0 ~ M - 1 次,考虑组合生成函数 f(x) = \sum\limits_{i=0}^{m-1} \frac {x^i} {i!} ,那么答案即 (N-2)![x^{N-2}]f^N(x)

READ MORE

考虑每一个标记一定对模 x 同余的所有数进行修改。

对于 x \le \sqrt n 的标记,我们维护出 x 相同的操作的 y 值前缀和,这样 x 相同的标记对当前查询的贡献就可以分为整块 + 前缀和 + 后缀和。

对于 x > \sqrt n 的标记,我们对原序列分块,则每一个修改一定在不同的块中,我们暴力修改 + 暴力统计每个块的和即可。

总时间复杂度 O(n \sqrt n) ,卡卡常可以通过此题。

READ MORE

原来的 Hexo 博客更新了很多没什么卵用的内容,而且主题也过于臃肿和花里胡哨了。

现在感觉搭建博客应该把时间专注于内容上,而不是魔改主题 / 写意义不大的文章 / 和刷垃圾评论的小学生打交道。

所以最后还是决定使用 Typecho 。非常巧的是,我最初开始写博客时,用的也是 Typecho ,可以说是折腾了一圈之后又回到了最初。

之前博客的大多数内容可以在 一句话题解 中找到。

如果你确实需要之前的博客,则可以前往 旧博客的备份

READ MORE

Burnside 引理

ans = { 1 \over |G| } \sum_{f \in G} C(f) ,其中 C(f) 表示置换 f 中不动点的个数

Polya 定理

定义 L(f) 为置换 f 的循环节数,可以理解为对于任意一种状态至多经过 L(f) 次置换 f 可以变回原样。

易证置换 f 的不动点一定满足其自身的循环节为 L(f) ,即 C(f) = k^{L(f)} ,其中 k 表示颜色种数。

Polya 定理的公式即 ans = { 1 \over |G| } \sum_{f \in G} k^{L(f)}

READ MORE

f_i 表示 i 个时的高度之和, g_i 表示 i 个时的方案数,显然:

\begin{aligned} g_n &= \sum\limits_{i=1}^n {n \choose i} g_{n-i} \\ f_n &= g_n + \sum\limits_{i=1}^n {n \choose i} f_{n-i} \\ ans_n &= f_n \times g_n^{-1} \end{aligned}

其实到这里可以直接分治 NTT ,不过我们考虑多项式求逆的做法。 首先把 {n \choose i} 拆开,然后设 F_n = f_n / n!G_n = g_n / n!H_n = 1 / n!

\begin{aligned} G &= (2 - H)^{-1} \\ F &= (G - 1) (2 - H)^{-1} \\ ans_n &= F_n G_n^{-1} \end{aligned}

(推导时需要注意常数项系数,f_0 = 0,g_0 = h_0 = 1。)

READ MORE

数据范围容易想到利用矩阵进行计算。

考虑 f(k) = (A, B) ,其中 A 表示恰好等于 k 的路径条数, B 表示小于等于 k 的路径条数。则可以这样转移: (A, B) \times (C, D) = (A \times C, B + A \times D)

需要注意的是,对长度为 L 的路径对答案的贡献可以表示为一个二次多项式(即 f(L) = L ^ 2),转移时不能直接计算,而需要记录一次项和常数项系数。注意多项式乘法时需要乘上组合数。

READ MORE

P(S) 为钦点 S 中所有元素都在 1 之后挂掉的概率,显然:

P(s) = \frac{a_1}{sum(S) + a_1}

于是我们可以发现最后答案为:

ans = \sum\limits_{S \in [2, n]} P(S) (-1)^{|S|}

于是分治 + NTT 即可。

至此除斗地主外的所有 PKUWC 2018 题目已经订正完毕,祝也去参加 PKUWC 的读者和自己 RP = +\infty qwq!

READ MORE

考虑 Min-Max 容斥,\min(S) 表示至少一个从 s 走到至少一个属于集合 S 的点的期望时间。

f(i, S) 表示集合 Si 到任意 u \in S 的期望时间,则 \min(S) = f(s, S)

f(i, S) = \begin{cases} 0 &(i \in S) \\\\ \frac{\sum_{i \to j} f(j, S)}{d_i} + 1 &(i \notin S) \end{cases}

可通过高斯消元求出,但复杂度过大不能接受。 考虑把原式化为 f(i) = k_i \times f(father_i) + b_i 的形式,推导过程略。 对于每个查询状压处理 \max(S) 不现实,需要处理出每个子集,FWT 一下即可 AC 。

READ MORE

Min-Max 容斥:

\max(S) = \sum\limits_{S' \subseteq S} \min(S') (-1)^{|S'| - 1}

可以用二项式反演证明:构造容斥函数 f(x) 使得

\max(S) = \sum\limits_{S' \subseteq S} \min(S') f(|S'|)

考虑每个 S' \subseteq S\min(S') = a_{x+1} 对答案的贡献为:

g(x) = [x = 0] = \sum\limits_{i=0}^x {x \choose i} f(i+1)

二项式反演得:

所以:

\begin{aligned} \max(S) &= \sum\limits_{S' \subseteq S} \min(S') f(|S'|) \\ &= \sum\limits_{S' \subseteq S} \min(S') (-1)^{|S'| - 1} \end{aligned}

READ MORE

之前特别喜欢那种动态博客,因为它能够提供一种更加简洁直观的编辑页面,而不是像 Hexo 一样,要从一堆 .md 文件中找出自己需要编辑的那个。

当然, Hexo 下这个问题也不是无解,所以这篇文章就来简单的介绍下在 Hexo 的文章管理插件。

READ MORE