Codeforces Round #829 (Div. 2) D. Factorial Divisibility
Let’s create an array [ c n t 1 , c n t 2 , … , c n t x ] [cnt_1,cnt_2,…,cnt_x] [cnt1,cnt2,…,cntx] where c n t i cnt_i cnti equals to number of elements equals to i in the initial array.
Note that a 1 ! + a 2 ! + … + a n ! a_1! +a_2! + … + a_n! a1!+a2!+…+an! equals to sum of k ! ⋅ c n t k k!⋅cnt_k k!⋅cntk over all k k k from 1 1 1 to x − 1 x−1 x−1, c n t x cnt_x cntx does not affect anything because x! divides x ! x! x! itself. We have to check if this sum is divisible by x ! x! x!.
Suppose there exists some k < x k<x k<x such that c n t k ≥ k + 1 cnt_k≥k+1 cntk≥k+1. In this case we can make two transformations: c n t k − = ( k + 1 ) cnt_k−=(k+1) cntk−=(k+1) ; c n t k + 1 + = 1 cnt_{k+1}+=1 cntk+1+=1 and the sum of k!⋅cntk will not change because ( k + 1 ) ⋅ k ! = ( k + 1 ) ! (k+1)⋅k!=(k+1)! (k+1)⋅k!=(k+1)!.
Let’s perform this operation until it is possible for all numbers from 1 1 1 to x − 1 x−1 x−1. After all operations the sum of k ! k! k!⋅ c n t k cnt_k cntk will not change and for each k < x k<x k<x the inequality c n t k ≤ k cnt_k≤k cntk≤k will be satisfied because if c n t k ≥ k + 1 cnt_k≥k+1 cntk≥k+1 we could perform an operation with this element.
Let’s see what is the maximum value of sum of k ⋅ c n t k k⋅cnt_k k⋅cntk over all k k k from 1 1 1 to x − 1 x−1 x−1 after all operations. We know that c n t k ≤ k cnt_k≤k cntk≤k for all k k k, so the maximum value of the sum is the sum of k ⋅ k ! k⋅k! k⋅k! over all k k k.
Note that k ⋅ k ! = ( ( k + 1 ) − 1 ) ⋅ k ! = ( k + 1 ) ⋅ k ! − k ! = ( k + 1 ) ! − k ! k⋅k!=((k+1)−1)⋅k!=(k+1)⋅k!−k!=(k+1)!−k! k⋅k!=((k+1)−1)⋅k!=(k+1)⋅k!−k!=(k+1)!−k!.
It means that the sum of such values over all k k k from 1 1 1 to x − 1 x−1 x−1 equals to ( 2 ! − 1 ! ) + ( 3 ! − 2 ! ) + … + ( x ! − ( x − 1 ) ! ) (2!−1!)+(3!−2!)+…+(x!−(x−1)!) (2!−1!)+(3!−2!)+…+(x!−(x−1)!). Each factorial from 2 2 2 to x − 1 x−1 x−1 will be added and subtracted from the sum. So the result is x ! − 1 x!−1 x!−1.
So the only one case when this sum is divisible by x ! x! x! is when the sum equals to 0 0 0. It means that c n t k cnt_k cntk equals to zero for all k k k from 1 1 1 to x − 1 x−1 x−1 after performing all operations.
Time complexity: O ( n + x ) O(n+x) O(n+x).
#include<bits/stdc++.h>
using namespace std;int main()
{int n,x;cin>>n>>x;vector<int> a(500010);for(int i=1;i<=n;i++){int k;cin>>k;a[k]++;}for(int i=1;i<=500000;i++){a[i+1]+=a[i]/(i+1);a[i]%=(i+1);}for(int i=1;i<=x-1;i++)if(a[i]){cout<<"No"<<endl;return 0;}for(int i=x;i<=500001;i++)if(a[i]){cout<<"Yes"<<endl;return 0;}return 0;
}
