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$ 数列的 $r{k}_x$ 不同。

$n\le 5\times {10}^5,a_i\le {10}^6$，时空限制：2s 256M。

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

考虑这么一个事情，

定义

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

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

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

下降幂和上升幂

$x$ 的 $k$ 次下降幂记作 $x^{\underset{―}{k}}$，表示的是 $\prod _{i=0}^{k-1}(x-i)$ 。

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