Codeforces Round 829 (Div. 2) - D. Factorial Divisibility (1600)

D. Factorial Divisibility

$a_i \ge x$라면 고려해주지 않는다. $x! \mid x! \cdot k$ 이기 때문이다.

모든 $a_i$가 나온 횟수를 기록한다. 이를 $c_i$ 라 한다.

만약 어떤 $i$에 대해 $c_i \ge i+1$ 이라면,

$1 \cdot 2 \cdots (i-1) \cdot i \cdot (i+1)$ 처럼 변형해줄 수 있다는 의미이므로

$c_{i+1}$ 을 업데이트해주고 $c_i$ 는 위로 보내준만큼 없애준다.

이때, $c_i \neq 0$ 이면 정답은 불가능하다이다.

$c_i\cdot i!\ (c_i \le i)$ 이 다른 수와 더해져서 $x!$ 로 나누어지려면

$c_i \cdot i! + T \ge x!$ 여야 한다.

$c_i \le i$ 이므로

$\displaystyle \sum_{i=1}^{x-1}i \cdot i! < x!$ 라 주장하자.

$x!-(x-1)! \cdot (x-1)=x \cdot (x-1)! -(x-1) \cdot (x-1)!=(x-1)!$ 이다.

귀납적으로 $\displaystyle \sum_{i=1}^{x-2}i \cdot i! < (x-1)!$ 일 것이므로(이 귀납법이 이런식으로 진행하면 안되고 $i=2$ 부터 기저를 잡아야 올바를 듯 어쨋든 이런식으로 증명하면 된다), 어떤 $T$ 를 가져와도 $x!$ 로 나누어지지 못하기 때문에 어떤 $c_i \neq 0$ 이라면 정답은 No이다.

에디토리얼에선 $\displaystyle \sum_{i=1}^{x-1}i \cdot i!=x!-1$ 임을 보여준다.

void solve() {  
   int n, x;  
   cin >> n >> x;  
   vi a(n);  
   fv(a);  
   vi cnt(555555);  
   for (int i: a) if (i < x) cnt[i]++;  
   for (int i = 1; i < x; i++) {  
      if (cnt[i]) {  
         int q = cnt[i] / (i + 1);  
         cnt[i + 1] += q;  
         cnt[i] -= q * (i + 1);  
  
         if (cnt[i]) {  
            cout << "No";  
            return;  
         }  
      }  
   }  
   cout << "Yes";  
}