CF1753B 题解

\(\mathcal Preface\)

题目传送门

\(\mathcal Solution\)

定理：\(n! \cdot (n+1) = (n+1)!\)

这题就是围绕以上定理展开的。

如果加入一个数 \(a_i\) 满足 \(\operatorname{count}(a_i) > a_i\)，则根据定理，将 \(\operatorname{count}(a_{i+1}) + 1\)，在将 \(a_i=0\)。其中 \(\operatorname{count}(a_i)\) 表示 \(a_i\) 出现的次数

如果 \(\sum\limits_{i=1}^{n}a_i! \mid x!\) 即满足 \(\left(\sum\limits_{i=1}^{x-1}\operatorname{count}(i)\right) = 0\)。

\(\mathcal Code\)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#include <sstream>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>

#define x first
#define y second
#define IOS ios::sync_with_stdio(false)
#define cit cin.tie(0)
#define cot cout.tie(0)

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 500010, M = 100010, MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LLINF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;

int n, x;
int cnt[N];

void solve()
{
	cin >> n >> x;
	for (int i = 1; i <= n; i ++ )
	{
		int t;
		cin >> t;
		cnt[t] ++ ;
		while (cnt[t] >= t + 1)
		{
			cnt[t + 1] += cnt[t] / (t + 1);
			cnt[t] %= (t + 1);
			t ++ ;
		}
	}
	
	bool flag = true;
	for (int i = 1; i < x; i ++ )
		if (cnt[i])
		{
			flag = false;
			break;
		}
	if (flag) cout << "Yes" << endl;
	else cout << "No" << endl;
}

int main()
{
	IOS;
	cit, cot;
	int T = 1;
//	cin >> T;
	while (T -- ) solve();
	return 0;
}