D. Factorial Divisibility
You are given an integer $x$ and an array of integers $a_1,a_2, \dots ,a_n$. You have to determine if the number $a_1!+a_2!+ \dots +a_n!$ is divisible by $x!$.
Here $k!$ is a factorial of $k$ — the product of all positive integers less than or equal to $k$. For example, $3! = 1 \cdot 2 \cdot 3 = 6$, and $5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120$.
Input
The first line contains two integers $n$ and $x$ $(1 \leq n \leq 500000, 1 \leq x \leq 500000)$.
The second line contains $n$ integers $a_1,a_2, \dots ,a_n$ $(1 \leq a_i \leq x)$ — elements of given array.
Output
In the only line print "$\text{Yes}$" (without quotes) if $a_1!+a_2!+ \dots +a_n!$ is divisible by $x!$, and "$\text{No}$" (without quotes) otherwise.
Examples
input
6 4 3 2 2 2 3 3
output
Yes
input
8 3 3 2 2 2 2 2 1 1
output
Yes
input
7 8 7 7 7 7 7 7 7
output
No
input
10 5 4 3 2 1 4 3 2 4 3 4
output
No
input
2 500000 499999 499999
output
No
Note
In the first example $3! + 2! + 2! + 2! + 3! + 3! = 6 + 2 + 2 + 2 + 6 + 6 = 24$. Number $24$ is divisible by $4!=24$.
In the second example $3! + 2! + 2! + 2! + 2! + 2! + 1! + 1! = 18$, is divisible by $3!=6$.
In the third example $7! + 7! + 7! + 7! + 7! + 7! + 7! = 7 \cdot 7!$. It is easy to prove that this number is not divisible by $8!$.
解题思路
这题还是比较难想的。开个数组统计每个$a_i$的出现次数，数组$[cnt_1, cnt_2, \ldots, cnt_x]$分别表示某个数字$i$出现的次数$cnt_i$（因为$1 \leq a_i \leq x$，因此统计的数就是$1 \sim x$）。那么$\sum\limits_{i=1}^{n}{a_i!}$就是$\sum\limits_{i=1}^{x}{{cnt}_{i} \cdot i!}$。这里我们只累加到$x-1$，即$\sum\limits_{i=1}^{x-1}{{cnt}_{i} \cdot i!}$，这是因为我们只关心这个和是否能被$x!$整除，又因为${cnt}_{x} \cdot x!$被$x!$整除，因此只需判断$\sum\limits_{i=1}^{x-1}{{cnt}_{i} \cdot i!}$能否被$x!$整除就可以了。
因为$(i + 1) \cdot i! = (i+1)!$，因此如果存在某个$cnt_i \geq i + 1$，那么我们让$cnt_i \mathrel{-}= i + 1$，$cnt_{i+1} \mathrel{+}= 1$，重复这个过程直到$cnt_i < i + 1$。从$1$枚举$x$，进行上面的操作，最后保证对于任意一个数$i$，有$cnt_i < i + 1$。
断言：对于$1 \leq i \leq x - 1$，如果存在某个$cnt_i \ne 0$，那么$\sum\limits_{i=1}^{x-1}{{cnt}_{i} \cdot i!}$不能被$x!$整除。注意到执行上面的操作后有$cnt_i < i + 1$，因此有$$\sum\limits_{i=1}^{x-1}{{cnt}_{i} \cdot i!} \leq \sum\limits_{i=1}^{x-1}{i \cdot i!}$$因为$i \cdot i! = ((i + 1) - 1) \cdot i! = (i + 1) \cdot i! - i! = (i + 1)! - i!$，因此$$\begin{align*} \sum\limits_{i=1}^{x-1}{{cnt}_{i} \cdot i!} &\leq \sum\limits_{i=1}^{x-1}{i \cdot i!} \\ &= 1 \cdot 1! + 2 \cdot 2! + \ldots + (x - 1) \cdot (x - 1)! \\ &= (2! - 1!) + (3! - 2!) + \ldots + (x! - (x-1)!) \\ &= x! - 1 \end{align*}$$即$\sum\limits_{i=1}^{x-1}{{cnt}_{i} \cdot i!} < x!$，自然不能被$x!$整除（很关键的一点）。
因此只要存在一个$cnt_i \ne 0$，那么$\sum\limits_{i=1}^{x-1}{{cnt}_{i} \cdot i!}$就不能被$x!$整除，即$\sum\limits_{i=1}^{n}{a_i!}$不能被$x!$整除。
AC代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 const int N = 5e5 + 10;
5
6 int cnt[N];
7
8 int main() {
9 int n, m;
10 scanf("%d %d", &n, &m);
11 while (n--) {
12 int x;
13 scanf("%d", &x);
14 cnt[x]++;
15 }
16 bool flag = true;
17 for (int i = 1; i < m; i++) {
18 if (cnt[i] % (i + 1)) {
19 flag = false;
20 break;
21 }
22 cnt[i + 1] += cnt[i] / (i + 1);
23 }
24 printf("%s", flag ? "YES" : "NO");
25
26 return 0;
27 }
参考资料
Codeforces Round #829 Editorial：https://codeforces.com/blog/entry/108336
标签：cnt,Divisibility,limits,leq,Factorial,sum,cdot,整除 From： https://www.cnblogs.com/onlyblues/p/16834339.html