Factorial Divisibility
Contest: Codeforces Round 829 (Div. 1)
Difficulty rating: 1600
Tags: math, number theory

You are given an integer $$$x$$$ and an array of integers $$$a_1, a_2, \ldots, a_n$$$. You have to determine if the number $$$a_1! + a_2! + \ldots + 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 format:
The first line contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 500\,000$$$, $$$1 \le x \le 500\,000$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le x$$$) — elements of given array.

Output format:
In the only line print "Yes" (without quotes) if $$$a_1! + a_2! + \ldots + a_n!$$$ is divisible by $$$x!$$$, and "No" (without quotes) otherwise.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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!$$$.

Example input:
6 4
3 2 2 2 3 3

Example output:
Yes

Example input:
8 3
3 2 2 2 2 2 1 1

Example output:
Yes

Editorial:
Let's create an array $$$[cnt_1, cnt_2, \ldots, cnt_x]$$$ where $$$cnt_i$$$ equals to number of elements equals to $$$i$$$ in the initial array.
Note that $$$a_1!\ + a_2!\ +\ \ldots\ +\ a_n!$$$ equals to sum of $$$k! \cdot cnt_k$$$ over all $$$k$$$ from $$$1$$$ to $$$x - 1$$$, $$$cnt_x$$$ does not affect anything because $$$x!$$$ divides $$$x!$$$ itself. We have to check if this sum is divisible by $$$x!$$$.
Suppose there exists some $$$k < x$$$ such that $$$cnt_k \geq k + 1$$$. In this case we can make two transformations: $$$cnt_k \mathrel{-}= (k + 1); cnt_{k+1} \mathrel{+}= 1$$$ and the sum of $$$k! \cdot cnt_k$$$ will not change because $$$(k+1) \cdot k! = (k+1)!$$$.
Let's perform this operation until it is possible for all numbers from $$$1$$$ to $$$x - 1$$$. After all operations the sum of $$$k! \cdot cnt_k$$$ will not change and for each $$$k < x$$$ the inequality $$$cnt_k \leq k$$$ will be satisfied because if $$$cnt_k \geq k+1$$$ we could perform an operation with this element.
Let's see what is the maximum value of sum of $$$k \cdot cnt_k$$$ over all $$$k$$$ from $$$1$$$ to $$$x - 1$$$ after all operations. We know that $$$cnt_k \leq k$$$ for all $$$k$$$, so the maximum value of the sum is the sum of $$$k \cdot k!$$$ over all $$$k$$$.
Note that $$$k \cdot k! = ((k + 1) - 1) \cdot k! = (k + 1) \cdot k! - k! = (k + 1)! - k!$$$.
It means that the sum of such values over all $$$k$$$ from $$$1$$$ to $$$x - 1$$$ equals to $$$(2! - 1!) + (3! - 2!) + \ldots + (x! - (x-1)!)$$$. Each factorial from $$$2$$$ to $$$x - 1$$$ will be added and subtracted from the sum. So the result is $$$x! - 1$$$.
So the only one case when this sum is divisible by $$$x!$$$ is when the sum equals to $$$0$$$. It means that $$$cnt_k$$$ equals to zero for all $$$k$$$ from $$$1$$$ to $$$x - 1$$$ after performing all operations.
Time complexity: $$$\mathcal{O}(n + x)$$$.