博主无聊时会出一些题目，难度不等。欢迎大家来玩！

注意：题目前带 * 的表示还没造完 / 已经投给某个比赛了，所以暂时不能查看。

简介

在数学中，某个序列 $(a_n)_{n \in {\mathbb{N}}}$ 的母函数（又称生成函数，英语：Generating Function）是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。使用母函数解决问题的方法称为母函数方法。

摘自维基百科。生成函数分为多种，本文将主要介绍普通生成函数（Ordinary Generating Function）和指数生成函数（Exponential Generating Function）。另外，本文还会提到大部分的多项式算法，用来解决生成函数的题目。

入门文章推荐：

• 浅谈生成函数之 OGF
• 浅谈生成函数之 EGF

前言

在 OI 中，许多涉及到生成函数的计数题都需要使用一些多项式算法，所以掌握多项式算法是必要的。

常见导数

简介

本文包括 IOI 2020 集训队作业 31 ~ 35 题的题解，下面是题单：

• 31.「AGC 030D」Inversion Sum
• 32.「AGC 030E」Less than 3
• 33.「AGC 030F」Permutation and Minimum
• 34.「AGC 031D」A Sequence of Permutations
• 35.「AGC 031E」Snuke the Phantom Thief
• 36.「AGC 031F」Walk on Graph

TorusSailing

「Topcoder 12984」TorusSailing

题目描述

有 $n \times m$ 的网格，一人从 $(1, 1)$ 随机游走，每次等概率向下或向右，问走到 $(x, y)$ 的期望步数。

数据范围：$n, m \le 100$。

「NOI 2018」你的名字（UOJ 395）

题目描述

给定字符串 $S$，$q$ 次询问给定 $(T, l, r)$，问 $T$ 有多少个本质不同的子串不在 $S$ 中出现。

数据范围：$\vert S \vert, \vert T \vert \le 5 \times 10^5, \sum \vert T \vert \le 10^6$。

「Codeforces 547E」Mike and Friends

题目描述

给定 $n$ 个串，$q$ 次询问 $(l, r, k)$，问第 $k$ 个串在第 $[l, r]$ 个串中作为子串出现了多少次。

数据范围：$n \le 2 \times 10^5, q \le 5 \times 10^5$。

简介

本文包括 IOI 2020 集训队作业 27 ~ 30 题的题解，下面是题单：

• 25.「AGC 028E」High Elements
• 26.「AGC 028F」Reachable Cells
• 27.「AGC 029C」Lexicographic constraints
• 28.「AGC 029E」Wandering TKHS
• 29.「AGC 029F」Construction of a tree
• 30.「AGC 030C」Coloring Torus

Sharti

「Codeforces 494E」Sharti

题目描述

$n \times n$ 的网格，给定 $m$ 个矩形，它们的并是白色的，剩下的格子是黑色的。两人博弈，每次可以选择一个边长不超过 $k$ 的正方形满足它的右下角是白色，然后反转这个正方形的颜色。不能操作者输，问先手是否必胜。

数据范围：$m \le 5 \times 10^4, k \le n \le 10^9$。

SetAndSet

「Topcoder 12004」SetAndSet

题目描述

给 $n$ 个数 $a_1, a_2, \cdots, a_n$，要把它们划分成两个集合，使得两边的 And 一样，问方案数。

数据范围：$n \le 50, 0 \le a_i < 2^{20}$。