标签 容斥 下的文章

「AtCoder Japan Alumni Group Summer Camp 2018 Day 2 K」Short LIS

题目链接：AtCoder Japan Alumni Group Summer Camp 2018 Day 2 K

给定 $n, a, b$，求满足如下条件的 $0 \sim n - 1$ 的排列 $P$ 的个数：

• $P$ 的最长上升子序列的长度至多为 $2$。
• $P_{a} = b$。

数据范围：$1 \le n \le 10 ^ {6}, 0 \le a, b < n$。

「UOJ 424」【集训队作业 2018】count

题目链接：UOJ 424

如果一个序列满足序列长度为 $n$，序列中的每个数都是 $1$ 到 $m$ 内的整数，且所有 $1$ 到 $m$ 内的整数都在序列中出现过，则称这是一个「挺好序列」。

对于一个序列 $A$，记 $f_{A}(l, r)$ 为 $A$ 的第 $l$ 个到第 $r$ 个数中最大值的下标（如果有多个最大值，取下标最小的）。

两个序列 $A$ 和 $B$ 同构，当且仅当 $A$ 和 $B$ 长度相等，且对于任意 $i \le j$，均有 $f_{A}(i, j) = f_{B}(i, j)$。

给出 $n, m$，求有多少种不同构的「挺好序列」。答案对 $998244353$ 取模。

数据范围：$1 \le n, m \le 10 ^ {5}$。

「Codeforces 1228E」Another Filling the Grid

题目链接：Codeforces 1228E

你有一个 $n \times n$ 的网格和一个整数 $k$，在每个格子中都填入一个整数，满足如下条件：

• 所有格子中的整数都介于 $1$ 到 $k$ 之间。
• 第 $i$ 行的最小值为 $1$（$1 \le i \le n$）。
• 第 $j$ 列的最小值为 $1$（$1 \le j \le n$）。

请求出填数的方案数，答案对 $10 ^ {9} + 7$ 取模。

数据范围：$1 \le n \le 250$，$1 \le k \le 10 ^ {9}$。

「TJOI 2019」唱、跳、rap 和篮球

题目链接：LOJ 3106

大中锋的学院要组织学生参观博物馆，要求学生们在博物馆中排成一队进行参观。

他的同学可以分为四类：一部分最喜欢唱、一部分最喜欢跳、一部分最喜欢 rap，还有一部分最喜欢篮球。如果队列中 $k, k + 1, k + 2, k + 3$ 位置上的同学依次，最喜欢唱、最喜欢跳、最喜欢 rap、最喜欢篮球，那么他们就会聚在一起讨论蔡徐坤。

大中锋不希望这种事情发生，因为这会使得队伍显得很乱。

大中锋想知道有多少种排队的方法，不会有学生聚在一起讨论蔡徐坤。两个学生队伍被认为是不同的，当且仅当两个队伍中至少有一个位置上的学生的喜好不同。

由于合法的队伍可能会有很多种，种类数对 $998244353$ 取模。

数据范围：$1 \le n \le 1000$，$0 \le a, b, c, d \le 500$，$a + b + c + d \ge n$。

「SPOJ 16607」IE1 - Sweets

题目链接：SPOJ 16607

John 有 $n$ 个水果罐子，每个罐子都装有不同种类的糖果，第 $i$ 个罐子里有 $m_i$ 个糖果。John 决定吃一些糖果，并且打算至少吃 $a$ 个，至多吃 $b$ 个，求一共有多少种吃法。答案对 $2004$ 取模。

数据范围：$1 \le n \le 10$，$0 \le a \le b \le 10 ^ 7$，$0 \le m_i \le 10 ^ 7$。

「ARC 102C」Stop. Otherwise...

题目链接：ARC 102C

Takahashi 有 $n$ 个骰子，每个骰子有 $k$ 个面分别标号为 $1$ 到 $k$。对于每个 $i = 2, 3, \dots, 2k$，求满足以下条件的方案数对 $998244353$ 的值。

• 投掷这 $n$ 个骰子，没有任何两个不同骰子的数字之和为 $i$。

注意骰子之间是相同的。也就是说，当存在整数 $k$ 使得两个方案数数字 $k$ 的骰子数量不同，那么这两个方案被认为是不同的。

数据范围：$2 \le n \le 2000$，$1 \le k \le 2000$。

「算法笔记」点分治

「AGC 005D」~K Perm Counting

题目链接：AGC 005D

给出 $n$ 和 $k$，求有多少个长度为 $n$ 的排列 $a$ 使得对于任意的 $1 \le i \le n$，都满足 $|a_i - i| \ne k$。

数据范围：$2 \le n \le 2000$，$1 \le k < n$。