|
|
## 抽屉原理,鸽巢原理
|
|
|
|
|
|
### 一、鸽巢原理
|
|
|
别名：鸽笼原理。狄利克雷抽屉原理。
|
|
|
|
|
|
最简单的一种形式：有$m + 1$只鸽子，$m$个笼子，那么至少有一个笼子有至少两只鸽子。当然，换个角度来说：有$m − 1$只鸽子，$m$个笼子，那么至少有一个笼子是空的。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
**初级加强**：有$m$个笼子，$k ∗ m + 1$只鸽子，那么至少有一个笼子有至少$k+1$只鸽子。
|
|
|
|
|
|
**高级加强**：
|
|
|
设$q_1,q_2,...,q_n$是正整数，如果有：
|
|
|
$$S_2=q_1+q_2+...+q_n-n+1$$
|
|
|
只鸽子需要放进$n$个笼子，那么或者第一个笼子至少有$q_1$只鸽子，或者第二个笼子至少有$q_2$只鸽子，...,或者第$q_n$个鸽笼至少有$q_n$只鸽子。
|
|
|
|
|
|
**反证法**
|
|
|
假设每个笼子里的鸽子数量都比题目要求的目标结果少一只：
|
|
|
|
|
|
即第 $i$ 个笼中最多有 $q_i−1$ 只鸽子，那么总共最多有：
|
|
|
$$S_1=(q_1−1)+(q_2−1)+⋯+(q_n−1)=q_1+q_2+⋯+q_n−n$$
|
|
|
|
|
|
此时发现$S_2=S_1+1$,也就是还有一只鸽子没有笼子，因此矛盾，所以假设错误，至少有一个笼子$i$,满足有$q_i$只鸽子。
|
|
|
|
|
|
### 二、 简单应用
|
|
|
（1）从一副纸牌（排除大小王）中随机抽取 $5$ 张纸牌，则至少存在两张牌的花色一致。
|
|
|
>**注意**:此时的 **鸽** 与 **笼** 分别指什么？
|
|
|
**鸽**：$5$ 张纸牌的各自花色，**笼**：$4$种花色；
|
|
|
|
|
|
（2）三个人分四块蛋糕，本着公平的原则，一定有一个人会分得 $2$ 块蛋糕；
|
|
|
|
|
|
（3）五个蛋糕要放在两个盒子里，则存在一个盒子存放的蛋糕数量至少为$3$.
|
|
|
$(5−1)2+1$（$5-1$：表示减去余出来的一个鸽子）
|
|
|
|
|
|
### 三、高级加强
|
|
|
任意给 $m$ 个整数$a_1,a_2,a_3,...,a_m$。
|
|
|
|
|
|
**求证**：必存在整数 $s,t(0≤s＜t≤m)$,使得 $m$ 整除 $a_{s+1}+a_{s+2}+…+a_t$。
|
|
|
> **解释**:就是在序列$a_1，a_2，……，a_m$中存在连续的$a_x$，使得这些$a$的和能够被$m$整除。
|
|
|
|
|
|
**证明**：
|
|
|
考虑$m$个和
|
|
|
$$\large a_1,a_1+a_2,a_1+a_2+a_3,……,a_1+a_2+a_3+...+a_m$$
|
|
|
|
|
|
如果这些和当中的 **任意一个可被$m$整除**，那么结论就成立。
|
|
|
|
|
|
那如果没有任意一个可以被$m$整除呢？
|
|
|
|
|
|
假设这些和中的每一个除以$m$都有一个非零余数，余数等于$1,2，……，m-1$ 中的一个数。因为有$m$个和，而只有$m-1$个余数，所以必然有两个和除以$m$有相同的余数。因此，存在整数 $s$和 $t$，$s<t$，使得$a_1+a_2+...+a_s$ 和 $a_1+a_2+...+a_t$除以$m$有相同的余数$r$：
|
|
|
|
|
|
$$
|
|
|
\large \left\{\begin{matrix}
|
|
|
a_1+a_2+...+a_s=b*m+r & \\
|
|
|
a_1+a_2+...+a_t=c*m+r &
|
|
|
\end{matrix}\right.
|
|
|
$$
|
|
|
|
|
|
二式相减，发现$a_{s+1}+a_{s+2}+……+a_t=(c-b)*m$，从而 $a_{s+1}+a_{s+2}+……+a_t$ 能够被$m$整除,证毕。
|
|
|
|
|
|
> **举栗子**：设$m=7$，且
|
|
|
> 整数为: $a[]=\{2,4,6,3,5,5,6\}$
|
|
|
> 前缀和: $s[]=\{2,6,12,15,20,25,31\}$
|
|
|
> 这些整数被$7$除时余数分别为
|
|
|
> $r[]=\{2,6,5,1,6,4,3\}$。有两个等于$6$的余数(位置是$2$和$5$)，这意味着结论：
|
|
|
> 从$2+1=3$开始，到$5$结束，有$a[3]+a[4]+a[5]=6+3+5=14$ 可被$7$整除。
|
|
|
|
|
|
### 四、鸽巢原理的应用
|
|
|
#### 1、练习题
|
|
|
一位洛谷$oier$要用$12$周的时间准备 $CTSC$,为了练习，他每天至少要刷一题，因为题目有难度，他每星期刷题无法超过$13$题。请你证明：存在连续的若干天期间，这位$oier$恰好刷了$11$题。
|
|
|
|
|
|
**证明**：
|
|
|
|
|
|
1.我们可以令$a_1$ 表示第一天所刷的题数，$a_2$ 表示前两天所刷的题数，$a_3$表示前三天所刷的题数.之后以此类推
|
|
|
|
|
|
2.而题目说，由于每天都要 **至少** 刷$1$题，所以数列
|
|
|
$$a_1<a_2<a_3<...<a_{84}$$
|
|
|
另有$a_1 >=1$.又每周最多刷$13$题，故$a_{84}< = 13 ∗ 12 = 156$。
|
|
|
|
|
|
因此又有：
|
|
|
$1 < = a_1 < a_2 < a_3 < . . . < a_{84} < = 156$
|
|
|
|
|
|
同理，
|
|
|
$a_1+11,a_2+11,a_3+11,...,a_{84} +11$同样是一个严格递增序列。范围：
|
|
|
$1+11 < = a_1+11 < a_2+11 < a_3+11 < . . . < a_{84}+11 < = 156+11$
|
|
|
$12<=a_1+11 < a_2+11 < a_3+11 < . . . < a_{84}+11<=167$
|
|
|
|
|
|
我们把两个序列合起来看：
|
|
|
$a_1 ,a_2,a_3,...,a_{84},a_1+11,a_2+11,a_3+11,...,a_{84} +11$
|
|
|
|
|
|
一共$168$个数。其中每一个数都是$1$到$167$之间的一个整数。
|
|
|
|
|
|
根据鸽巢原理可得，其中必有两个数相等！！！
|
|
|
|
|
|
同时$a_1,a_2,a_3,...,,a_{84}$中必然无相等的两个数，
|
|
|
而$a_1+11,a_2+11,a_3+11,...,a_{84} +11$中也是一样没有相等的两个数，那么，必然存在一个$x$和$y$,使得
|
|
|
$$\large a_x=a_y+11$$
|
|
|
|
|
|
从而得出结论：这个$oier$在第$y+1,y+2,y+3,...,x$天内一共刷了$11$道题。
|
|
|
|
|
|
#### 2、练习题
|
|
|
证明：在边长为$2$的等边三角形 **内部** 放上$5$个点。则至少存在两个点，他们之间的距离小于等于$1$.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
我们先画出一个边长为$2$的等边三角形。
|
|
|
|
|
|
然后把三条边中点两两相连。就形成了这张图。
|
|
|
|
|
|
那么根据鸽巢原理，必然有两个点在一个边长为$1$的小三角形里。
|
|
|
|
|
|
而我们知道，边长为$1$的等边三角形里处处距离都小于等于$1$,于是问题就解决了
|
|
|
|
|
|
> $5$个鸽子，$4$个笼子。
|
|
|
|
|
|
#### 3、练习题
|
|
|
已知$n+1$个正整数，它们全都小于或等于$2n$，**证明当中一定有两个数是互质的**。
|
|
|
|
|
|
要证明这个问题，我们就要利用一个互质的特性：**两个相邻整数互质**。
|
|
|
|
|
|
有了这个突破口，于是我们可以构造$n$个鸽巢，每一个里依次放入
|
|
|
$1,2,3,4,...,2n$
|
|
|
|
|
|
这$2n$个数中的两个数。
|
|
|
|
|
|
|
|
|
|
|
|
也就是说，我们要在这其中取出$n + 1$个数。
|
|
|
|
|
|
根据鸽巢原理，无论如何，我们都会抽空一个鸽巢。
|
|
|
|
|
|
一个鸽巢中的两个数肯定互质，所以问题就解决了。
|
|
|
|
|
|
> **扒栗史**：匈牙利大数学家厄杜斯($PaulErdous$,$1913 - 1996$) 向当年年仅$11$岁的波萨($LouisPósa$)提出这个问题，而小波萨思考了不足半分钟便能给出正确的答案。
|
|
|
|
|
|
|
|
|
> **冷笑话**：
|
|
|
> 山东高考$2017$年有$54$万人。而人的头发大约有$8−12$万根。那么必然有两人的头发数量相同。
|
|
|
|
|
|
|
|
|
#### 4、练习题
|
|
|
$NOIP$ 提高组 初赛 问题求解 习题集 $2010$ 第$3$题
|
|
|
|
|
|
记$T$为一队列，初始时为空，现有$n$个 **总和** 不超过$32$的正整数依次入列。如果无论这些数具体为何值，**都能找到一种出队的方式** ，使得存在某个时刻队列$T$中的数之和恰好为$9$，那么$n$的最小值是___________。
|
|
|
|
|
|
答案：
|
|
|
|
|
|
$18$
|
|
|
|
|
|
**题解**：
|
|
|
|
|
|
题意有些难懂：是指在数字尽可能取小，$n$尽可能长的情况下，符合题意的最大$n$值。
|
|
|
|
|
|
位置 `1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17`
|
|
|
数值 `1 1 1 1 1 1 1 1 (10) 1 1 1 1 1 1 1 1`
|
|
|
前缀和`1 2 3 4 5 6 7 8 18 19 20 21 22 23 24 25 26`
|
|
|
|
|
|
位置$9$取值是$10$的原因是，**起刁难作用**，让数组元素前缀和尽量的达不到$9$.
|
|
|
又因为，总的前缀和是$32$,故位置$9$的 **最小取值** 是$10$.
|
|
|
|
|
|
位置$10$开始，都用尽可能小的正数，故$1$最理想。
|
|
|
可以设置数据到数组的第$17$位元素，此时还是无法打成某段前缀和是$9$.
|
|
|
|
|
|
和是$32$,前$17$位已经用去了$26$，还剩下$6$,故第$18$位可以获得的数据是$1,2,3,4,5,6$
|
|
|
|
|
|
若第$18$位数值是$1$,
|
|
|
位置`10 11 12 13 14 15 16 17 18`
|
|
|
数值`1 1 1 1 1 1 1 1 1`
|
|
|
位置$10$到位置$18$可以构成和值为`1+1+1+1+1+1+1+1+1=9`.
|
|
|
|
|
|
|
|
|
若第$18$位数值是$2$,
|
|
|
位置`11 12 13 14 15 16 17 18`
|
|
|
数值`1 1 1 1 1 1 1 2`
|
|
|
位置$11$到位置$18$可以构成和值为`1+1+1+1+1+1+1+2=9`.
|
|
|
|
|
|
若第$18$位数值是$3$,
|
|
|
位置`12 13 14 15 16 17 18`
|
|
|
数值`1 1 1 1 1 1 3`
|
|
|
位置$11$到位置$18$可以构成和值为`1+1+1+1+1+1+3=9`.
|
|
|
|
|
|
若第$18$位数值是$4$,
|
|
|
位置`13 14 15 16 17 18`
|
|
|
数值`1 1 1 1 1 4`
|
|
|
位置$11$到位置$18$可以构成和值为`1+1+1+1+1+4=9`.
|
|
|
|
|
|
|
|
|
若第$18$位数值是$5$,
|
|
|
位置`14 15 16 17 18`
|
|
|
数值`1 1 1 1 5`
|
|
|
位置$11$到位置$18$可以构成和值为`1+1+1+1+5=9`.
|
|
|
|
|
|
若第$18$位数值是$6$,
|
|
|
位置`15 16 17 18`
|
|
|
数值`1 1 1 6`
|
|
|
位置$11$到位置$18$可以构成和值为`1+1+1+6=9`.
|
|
|
|
|
|
很明显，在极端条件下，符合题意的$n$值，是$18$.
|
|
|
|
|
|
#### 5、练习题
|
|
|
从整数$1,2,...,200$中选出$101$个整数。
|
|
|
**求证**：在所选的这些整数之间存在两个这样的整数，其中的一个可被另一个整除。
|
|
|
|
|
|
首先要先知道这点：任一整数都可以写成的$2^k*a$形式，其中$k>=0\&\&a$是奇数。
|
|
|
|
|
|
对于$1$到$200$之间的一个整数，$a$是$100$个数$1,3,5，...，199$中的一个。因此，在所选的$101$个整数中存在两个整数，当写成上述形式时这两个数具有相同的$a$值。令这两个数是$2^r*a$和$2^s*a$，如果$r<s$,那么第二个数就能被第一个数整除。反之亦然。
|
|
|
|
|
|
注意，从$1,2，...，200$中可以选择$100$个数，使得其中没有一个能被另一个数整除（比如，这$100$个整数是$101,102，...，119,200$）
|
|
|
|
|
|
### 五、$Ramsey$定理
|
|
|
> **扒栗史**：此定理由$Frank$ $Plumpton$ $Ramsey$（弗兰克·普伦普顿·拉姆齐，$1903−1930$）提出.
|
|
|
|
|
|
此定理有一个广为流传的例子：$6$ 个人中至少存在$3$人相互认识或者相互不认识。
|
|
|
|
|
|
**转换**：该定理等价于证明这$6$个顶点的完全图的边，用红、蓝二色任意着色，必然至少存在一个红色边三角形，或蓝色边三角形
|
|
|
|
|
|
|
|
|
|
|
|
### 六、与编程结合的题目
|
|
|
|
|
|
**[$HDU$ $1808$ $Halloween$ $treats$](https://acm.hdu.edu.cn/showproblem.php?pid=1808)**
|
|
|
|
|
|
**题目大意**：
|
|
|
|
|
|
给你两个整数$C$和$N$，再给你$N$个正数的序列，从中找到若干数，使得其和刚好是 $C$ 的倍数。输出这些数的序号。
|
|
|
|
|
|
我们知道$C<=N$的，故我们可以用鸽巢原理去做，
|
|
|
|
|
|
**思路**：
|
|
|
|
|
|
$Sum[i]$为序列中前 $i$ 项的和。则有两种可能：
|
|
|
|
|
|
1.若有 $Sum[i]$ 是 $C$ 的倍数，则直接输出前 $i$ 项。
|
|
|
|
|
|
2.如果没有任何的 $Sum[i]$ 是 $C$ 的倍数，则计算 $ri = Sum[i] \% C$。根据鸽巢原理，肯定有 $Sum[i] \% C == Sum[j] \% C，j<i$。则第 $j +1$项到第 $i$ 项数的和即为 $C$ 的倍数。
|
|
|
|
|
|
这题说，要是没答案就输出 `no sweets` ，想想，这有可能吗？
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 1e5 + 100;
|
|
|
int sum[N], mod[N];
|
|
|
int main() {
|
|
|
ios::sync_with_stdio(false);
|
|
|
int c, n;
|
|
|
while (cin >> c >> n, c + n) {
|
|
|
memset(mod, -1, sizeof mod);
|
|
|
memset(sum, 0, sizeof sum);
|
|
|
mod[0] = 0;
|
|
|
|
|
|
int s = 0, t = 0;
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
int x;
|
|
|
cin >> x;
|
|
|
sum[i] = (sum[i - 1] + x) % c; // 前缀和 %c
|
|
|
|
|
|
if (sum[i] == 0) {
|
|
|
t = i;
|
|
|
continue;
|
|
|
}
|
|
|
|
|
|
if (mod[sum[i]] == -1)
|
|
|
mod[sum[i]] = i; // 首次出现这个余数
|
|
|
else { // 多次出现此余数
|
|
|
s = mod[sum[i]]; // 开始位置
|
|
|
t = i; // 结束位置
|
|
|
}
|
|
|
}
|
|
|
for (int i = s + 1; i <= t; i++)
|
|
|
cout << i << (i != t ? " " : "\n");
|
|
|
}
|
|
|
}
|
|
|
```
|
|
|
|
|
|
**[$HDU$ $1205$ 吃糖果](http://acm.hdu.edu.cn/showproblem.php?pid=1205)**
|
|
|
|
|
|
**方法**：隔板法求解
|
|
|
|
|
|
找出数量最多的一种糖果，把数量$n$看成$n$个隔板，隔成$n$个空间（隔板以右为一空间），其他糖果数量总和记为数值$s$。
|
|
|
|
|
|
（1）若$s<n-1$，把$s$个糖果放到隔板之间，$n$个隔板不够放，至少一个空间内没有糖果，因为两个隔板为同一种糖果，不符合题意，无解。
|
|
|
|
|
|
（2）若$s>=n-1$，有解。
|
|
|
|
|
|
推导之后发现：当总数-最大值>=最大值-1时，就满足有解条件。
|
|
|
|
|
|
**注意事项**：
|
|
|
|
|
|
（1）用数组存放时，数组要开大，$n<=1000000$，数组要$a[1000000]$；
|
|
|
|
|
|
（2）把$t,n$等变量定义成`long long`类型（$int$类型的话为$WA$）。
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
#define int long long
|
|
|
const int N = 1000010;
|
|
|
int a[N];
|
|
|
signed main() {
|
|
|
int T;
|
|
|
cin >> T;
|
|
|
while (T--) {
|
|
|
int n, sum, mx;
|
|
|
cin >> n;
|
|
|
sum = 0, mx = 0;
|
|
|
for (int j = 0; j < n; j++) {
|
|
|
cin >> a[j];
|
|
|
sum += a[j];
|
|
|
mx = mx < a[j] ? a[j] : mx;
|
|
|
}
|
|
|
if ((sum - mx) >= (mx - 1))
|
|
|
puts("Yes");
|
|
|
else
|
|
|
puts("No");
|
|
|
}
|
|
|
}
|
|
|
```
|
|
|
|
|
|
**[$HDU$ $5917$ $Instability$](http://acm.hdu.edu.cn/showproblem.php?pid=5917)**
|
|
|
|
|
|
> 前导知识：
|
|
|
> **[离散数学 --- 图论基础 --- 子图和补图，握手定理](https://blog.csdn.net/qq_51947882/article/details/126751352)**
|
|
|
>
|
|
|
**题意**：给出一个图，求稳定子图的个数。稳定子图定义为包含三元环子图或者三个点独立集子图的图。
|
|
|
|
|
|
**题解**：
|
|
|
$Ramsey$定理的通俗表述： $6$ 个人中至少存在$3$人相互认识或者相互不认识。所以对于大于$6$的子集都是满足条件的，组合数算一下就好，对于小于$6$的子集，最多是$n$的5次方，直接暴力。
|
|
|
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
#define int long long
|
|
|
#define endl "\n"
|
|
|
|
|
|
const int M = 1e2 + 7;
|
|
|
const int P = 1e9 + 7;
|
|
|
|
|
|
int T, n, m, cas = 1;
|
|
|
int g[M][M];
|
|
|
int fac[M];
|
|
|
|
|
|
// 快速幂
|
|
|
int qmi(int a, int b) {
|
|
|
int res = 1;
|
|
|
a %= P;
|
|
|
while (b) {
|
|
|
if (b & 1) res = res * a % P;
|
|
|
b >>= 1;
|
|
|
a = a * a % P;
|
|
|
}
|
|
|
return res;
|
|
|
}
|
|
|
|
|
|
/*
|
|
|
Q:什么是费马小定理?
|
|
|
答：费马小定理是一个关于模运算的定理，它陈述了如果p是一个质数，而a是任意整数且不是p的倍数，
|
|
|
那么a^(p-1) 与 1 (mod p) 同余。
|
|
|
|
|
|
Q:费马小定理是怎么求逆元的？
|
|
|
答：当p是质数时，我们分离一项出来
|
|
|
a * a^(p−2) ≡ 1 (mod p)
|
|
|
对比逆元的方程式，可以很容易得到，a关于p的逆元就是 a^(p −2),而a^(p-2)可以用快速幂求得
|
|
|
|
|
|
Q:组合数公式C(n,m)=n!/(m!*(n-m)!) ，由于需要取模，同时存在除法，所以可以考虑是否可以用费马小定理求除法逆元？
|
|
|
答：是可以的，原因：因为模mod=1e9+7是质数，并且，题目中的数据范围n<=50,是不可能是mod的倍数的，所以符合费马小定理
|
|
|
的要求，可以用费马小定理来求除法逆元。
|
|
|
*/
|
|
|
int C(int n, int m) {
|
|
|
/*
|
|
|
fac[n]: n!
|
|
|
qmi(fac[m], P - 2) : 费马小定理的结果 (m!)^(p-2),这样，把除m!取模 转化为乘 (m!)^(p-2)后取模
|
|
|
qmi(fac[n - m], P - 2) :同上
|
|
|
*/
|
|
|
return fac[n] * qmi(fac[m], P - 2) % P * qmi(fac[n - m], P - 2) % P;
|
|
|
}
|
|
|
|
|
|
int judge3(int i, int j, int k) { // 判断三点之间满不满足不稳定点集
|
|
|
if (g[i][j] && g[i][k] && g[j][k]) return 1; // 三点之间相连
|
|
|
if (!g[i][j] && !g[i][k] && !g[j][k]) return 1; // 三点之间不互连
|
|
|
return 0;
|
|
|
}
|
|
|
|
|
|
int judge4(int i, int j, int k, int l) {
|
|
|
if (judge3(i, j, k) || judge3(i, j, l) || judge3(j, k, l) || judge3(i, k, l)) return 1;
|
|
|
// 表示4个点中有三个点为不稳定点集就行,为什么呢？
|
|
|
// 因为时题目要求的，不稳定点集为3个点。
|
|
|
return 0;
|
|
|
}
|
|
|
|
|
|
int judge5(int i, int j, int k, int l, int o) {
|
|
|
// 表示5个点中有4个点满足就行
|
|
|
if (judge4(i, j, k, l) || judge4(i, j, k, o) || judge4(i, j, l, o) || judge4(j, k, l, o)
|
|
|
|| judge4(i, k, l, o)) return 1;
|
|
|
return 0;
|
|
|
}
|
|
|
|
|
|
void solve() {
|
|
|
cin >> n >> m; // n个顶点,m条边
|
|
|
memset(g, 0, sizeof g); // 初始化地图
|
|
|
|
|
|
while (m--) {
|
|
|
int a, b;
|
|
|
cin >> a >> b;
|
|
|
g[a][b] = g[b][a] = 1; // 无向图
|
|
|
}
|
|
|
int ans = 0;
|
|
|
|
|
|
if (n >= 6) {
|
|
|
ans = qmi(2, n);
|
|
|
// ① 多项式定理C(n,0)+C(n,1)+...+C(n,n)=2^n
|
|
|
// ② 也可以这样来思考，一个也不要，要1个，要2个，要3个，...,要n个
|
|
|
|
|
|
// C(n,k)(k>=6)表示，从n个中取k个出来，总存在一个不稳定点集的个数（三点之间互联或三点之间不连）
|
|
|
for (int i = 0; i < 6; i++) /// 减去前5个
|
|
|
ans = (ans - C(n, i) + P) % P;
|
|
|
}
|
|
|
|
|
|
if (n >= 3) { // 枚举任意3个
|
|
|
for (int i = 1; i <= n; i++)
|
|
|
for (int j = i + 1; j <= n; j++)
|
|
|
for (int k = j + 1; k <= n; k++)
|
|
|
if (judge3(i, j, k)) ans = (ans + 1) % P;
|
|
|
}
|
|
|
|
|
|
if (n >= 4) { // 暴力取4个
|
|
|
for (int i = 1; i <= n; i++)
|
|
|
for (int j = i + 1; j <= n; j++)
|
|
|
for (int k = j + 1; k <= n; k++)
|
|
|
for (int l = k + 1; l <= n; l++)
|
|
|
if (judge4(i, j, k, l)) ans = (ans + 1) % P;
|
|
|
}
|
|
|
|
|
|
if (n >= 5) { // 暴力取5个
|
|
|
for (int i = 1; i <= n; i++)
|
|
|
for (int j = i + 1; j <= n; j++)
|
|
|
for (int k = j + 1; k <= n; k++)
|
|
|
for (int l = k + 1; l <= n; l++)
|
|
|
for (int o = l + 1; o <= n; o++)
|
|
|
if (judge5(i, j, k, l, o)) ans = (ans + 1) % P;
|
|
|
}
|
|
|
printf("Case #%lld: %lld\n", cas++, ans);
|
|
|
}
|
|
|
|
|
|
signed main() {
|
|
|
// 加快读入
|
|
|
ios::sync_with_stdio(false), cin.tie(0);
|
|
|
|
|
|
// 预处理阶乘数组（同步取模）
|
|
|
fac[0] = 1, fac[1] = 1;
|
|
|
for (int i = 2; i < M; i++) fac[i] = fac[i - 1] * i % P;
|
|
|
|
|
|
cin >> T;
|
|
|
while (T--) solve();
|
|
|
}
|
|
|
```
|
|
|
|
|
|
https://blog.csdn.net/LJD201724114126/article/details/84547302
|
