Codeforces Round #829 Div. 2 D. Factorial Divisibility(结论&数学)

Codeforces Round #829 Div. 2 D. Factorial Divisibility(结论&数学)

注意$1\le a_i\le x$

显然$a_i=x$没有影响。

那么只需考虑$[1,x-1]$这一部分的和。

注意到：$i!\times (i+1)=(i+1)!$

我们开个数组统计每个$i$的次数。

然后用上面的公式转化。这样保证每个$cn{t}_i\le i$

考虑${\sum }_{i=1}^{x-1}cn{t}_i\times i!$的最大值。

显然是$cn{t}_i=i$

那么${\sum }_{i=1}^{x-1}i\times i!=\sum (i+1-1)\times i!=(i+1)!-i!$ 可以错位相减。

然后 ∑ i = 1 x − 1 i × i ! = max ⁡ { ∑ c n t i × i ! } = x ! − 1 < x ! \sum_{i=1}^{x-1}i\times i!=\max\{\sum cnt_i\times i!\}=x!-1∑i=1x−1​i×i!=max{∑cnti​×i!}=x!−1<x!

那么如果要整除$x!$，显然这个部分要是$x!$的倍数，然后最大值都小于$x!$，所以只能等于0.

然后$O(n)$扫一遍即可。

// Problem: D. Factorial Divisibility
// Contest: Codeforces - Codeforces Round #829 (Div. 2)
// URL: https://codeforces.com/contest/1754/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Date: 2022-11-11 16:22:51
// --------by Herio--------

#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
const int hashmod[4] = {402653189,805306457,1610612741,998244353};
#define mst(a,b) memset(a,b,sizeof a)
#define db double
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define x first
#define y second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define VI vector<int>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr) 
void Print(int *a,int n){
	for(int i=1;i<n;i++)
		printf("%d ",a[i]);
	printf("%d\n",a[n]); 
}
template <typename T>		//x=max(x,y)  x=min(x,y)
void cmx(T &x,T y){
	if(x<y) x=y;
}
template <typename T>
void cmn(T &x,T y){
	if(x>y) x=y;
}
int main(){
	int n,x;
	IOS;
	cin>>n>>x;
	vector<int>a(x+1);
	for(int i=1;i<=n;i++){
		int y;cin>>y;
		a[y]++;
	}
	int ok  =1;
	for(int i=1;i<x;i++){
		while(a[i]>i){
			a[i]-=i+1;
			a[i+1]++;
		}
		if(a[i]){
			ok = 0;break;
		}
	}
	if(ok)cout<<"Yes";
	else cout<<"No";
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64