标签 容斥 下的文章
- 首页
- 容斥
「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$。