AcWing 3481. 阶乘的和
原题链接
简单
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 1e6 + 10;
int t, n, m, k, l, r, op, x, y;
int f[N], siz, pre[N];
bool flag;
bool dfs(int l, int t) {
if (f[l] == 0)return t == 0;
bool res = dfs(l + 1, t);
if (t <= pre[siz - 1] - pre[l - 1]) {
res = res | dfs(l + 1, t - f[l]);
}
return res;
}
void solve() {
f[0] = pre[0] = siz = 1;
for (int i = 1; i * f[i - 1] < N; i++) {
f[i] = f[i - 1] * i;
pre[i] = pre[i - 1] + f[i];
siz++;
}
// for(int i = 0;i<siz;i++){
// cout<<i<<" "<<f[i]<<"\n";
// }
while (cin >> n && n >= 0) {
if (n == 0)cout << "NO";
else cout << (dfs(0, n) ? "YES" : "NO");
cout << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
solve();
return 0;
}