Daniel_yuan's Blog

九条可怜老师吉老师在他的博客中大力赞扬 UR 。

于是博主就决定慢慢把 UR 补完。

希望补完之后能有吉老师十分之一的水平。

Day 1

划分数就是把一个数 \(n\) 拆分成若干个正整数的和的方案数，其中这若干个正整数是无序的，也就是 \(\{1,1,2\}\) 和 \(\{1,2,1\}\) 是等价的拆分。

下面我们来讨论怎么求它。

数据结构的一些小 trick。

本意是在联赛前记录些什么。

因为博主太懒所以咕了。

题目链接

题意简述

定义若二元组 \((a,b)<(c,d)\)，则有 \(a>c\) 或者 \(a=c \text{ and } b<d\)。

给你 \(n\) 个数，第 \(i\) 个数是 \(a_i\)。

现在系统会生成 \(n\) 个二元组，第 \(i\) 个二元组是 \((a_i,i)\) 或者是 \((a_i+1,i)\)，然后给每个二元组一个排名，设排名数列为 \(rk\)。

求有多少种不同的 \(rk\) 数列，两个 \(rk\) 序列不同当且仅当存在至少一个位置 \(x\)，使得两个 \(rk\) 数列的 \(rk_x\) 不同。

\(n\leq 5\times 10^5,a_i\leq 10^6\)，时空限制：2s 256M。

如果我们需要求维度为 \(c\) 的矩阵 \(A\) 的 \(m\) 次幂，那么一个显然的方法是用快速幂，复杂度为 \(c^3 \log m\)。不过当需要用到高精度的时候，该算法速度会大大下降。

考虑这么一个事情，

定义

PAM (Palindrome Automaton) 是一种处理回文串的、针对某个串的自动机，它保存了该串所有回文串的信息。

PAM 需要维护三个基础的东西：点、转移边、fail 边。PAM 和 AC 自动机类似，所以我们可以借鉴 AC 自动机来理解这些东西。

有一类多项式题，十分考验选手的推式子能力，真正的代码部分仅仅只是几个模板拼凑在一起。这类题目如果出现，往往会造成比较大的分差，所以在此略微归纳一下这类题目的做法。大致如下：

下降幂和上升幂

\(x\) 的 \(k\) 次下降幂记作 \(x^{\underline{k}}\)，表示的是 \(\prod_{i=0}^{k-1}(x-i)\) 。

\(x\) 的 \(k\) 次上升幂记作 \(x^{\overline{k}}\)，表示的是 \(\prod_{i=0}^{k-1}(x+i)\)。