Factorial Divisibility(数论,1600)

You are given an integer xx and an array of integers a1,a2,…,anYou have to determine if the number a1!+a2!+…+an! is divisible by x!.

Here k!k! is a factorial of k — the product of all positive integers less than or equal to kk. For example, 3!=1⋅2⋅3=63!=1⋅2⋅3=6, and 5!=1⋅2⋅3⋅4⋅5=120.

Input

The first line contains two integers n and x (1≤n≤500000, ).

The second line contains n integers a1,a2,…,an (1≤ai≤x) — elements of given array.

Output

In the only line print "Yes" (without quotes) if a1!+a2!+…+an! is divisible by x!, and "No" (without quotes) otherwise.

思路：

一开始一直想将阶乘的和转化为乘积的形式求解，未果。

正解：

先开桶记录下1~x-1的数量cnt[k]。不难发现当cnt[k]>=k+1时，可以做以下两个操作

cnt[k]-=k+1;cnt[k+1]+=1; 

k!*(k+1)=(k+1)!

直至cnt[k].（1=

#include
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=5e5+10;
int a[N],t[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n,x;
    cin>>n>>x;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        t[a[i]]++;
    }
    for(int i=1;i
        if(t[i]>i){
            t[i+1]+=t[i]/(i+1);
            t[i]%=i+1;
        }
        if(t[i]) {cout<<"NO\n";return 0;}
    }
    cout<<"YES\n";
    return 0;
}