Sum of Factorials

while True:
    try:
        num = int(input())
        factor = [1]*10
        for i in range(2,10):        #因为输入最大1000000，所以前十个阶乘就可以了
            factor[i] = factor[i-1]*i
        index = 9
        while index >= 0:            #一直减，能减就减，因为阶乘大于其前面所有阶乘的和
            if num >= factor[index]:
                num -= factor[index]
            index -= 1
        if num == 0:                 #如果减空了说明能分解为阶乘之和
            print('YES')
        else:
            print('NO')
    except Exception:
        break

#include<iostream>
using namespace std;
int main()
{
    int n;
    int fac[10]={1};
    for(int i=1;i<10;fac[i++]=fac[i-1]*i);
    while(cin>>n)
    {
        for(int i=9;i>=0;n<fac[i] ? i--:n-=fac[i--]);
        n==0 ? cout<<"YES"<<endl:cout<<"NO"<<endl;
    }
}

#include<stdio.h>//依题之意判断n是否等于连续的阶乘和
int main()//10的阶乘为3628800,n一定小于10的阶乘,所以算出10以前的阶乘即可
{
    int n,i,a[10];//a[i]代表i的阶乘
    a[0]=1;
    for(i=1;i<10;i++)//求1-9的阶乘
        a[i]=a[i-1]*i;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=9;i>=0;i--)//添加一个n==0时结束循环的语句也可以
            if(n>=a[i])
                n-=a[i];
        if(n==0)
            printf("YES\n");
        else
            printf("NO\n");
    }
}

能减就减，因为n！一定大于前n - 1个数的阶乘的和

#include<iostream>
using namespace std;

int f[10];

int main(){
    f[0] = 1;
    for(int i = 1; i < 10; i++)
        f[i] = f[i - 1] * i;
    int n;
    while(cin >> n){
        for(int i = 9; i >= 0; i--){
            if(n >= f[i]){
                n -= f[i];
            }
        }
        if(n == 0){
            cout << "YES" << endl;
        }
        else{
            cout << "NO" << endl;
        }
    }
    return 0;
}

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);

    int fact[10];

    fact[0] = fact[1] = 1;

    for(int i=2;i<10;i++)
    {
        fact[i] = fact[i-1]*i; 
    }

    bool seq[1000001];

    for(int i=0;i<=1000000;i++)
    {
        seq[i] = false;
    }

    for(int i=0;i<1024;i++)
    {
        int t = i;
        int sum = 0;
        for(int i=0;i<10;i++)
        {
            if(t%2==1)
                sum += fact[i];
            t /= 2; 
        }
        seq[sum]=true;    
    }

    int n;
    cin >> n;

    if(seq[n]==true)
        cout << "YES";
    else
        cout << "NO"; 

    return 0; 
}

其实就是先把所有可以表示的数算出来。一共就10个元素，所有的组合算出来也就2^10个数需要算，每一种组合都可以用0（或1）——1023中的一个数表示。

//用递归写的
#include<iostream>
using namespace std;
#include<vector>

vector<int> fac;
void init(){
    int t=1;
    fac.push_back(t);
    for(int i=1;t<=1000000;i++){
        t *= i;
        fac.push_back(t);
    }
}

bool solve(int m, int maxf){
    if(m==0)return true;
    else if(m<0)return false;
    if(maxf<0)return false;
    
    return solve(m-fac[maxf],maxf-1) || solve(m,maxf-1);
    
}
int main(){
    int num;
    init();
    while(cin>>num){
        int maxf=fac.size();
        while(fac[maxf]>num)
            maxf--;
        cout<<(solve(num,maxf)?"YES":"NO")<<endl;
    }
        
}

	#include <iostream>



	using namespace std;



	int main() {



	    int n, i;



	    int a[11];



	    a[0] = 1;



	    for (int i = 1; i <= 10; i++) {



	        a[i] = a[i - 1] * i;



	    }



	    while (cin >> n) {



	        for (int i = 10; i >= 0; i--) {



	            if (n >= a[i]) {



	                n -= a[i];



	            }



	        }



	        if (n > 0) {



	            cout << "NO" << endl;



	        }



	        else {



	            cout << "YES" << endl;



	        }



	    }



	    return 0;



	}

#include <stdio.h>
(737)#include <string.h>

const int N = 1000000;
const int M = 11;
int n;
int fact[M];
int maxIndex = 0;

bool ans = false;

void DFS(int curIndex,int sum) {
	if(curIndex > maxIndex || sum + fact[curIndex] > n)	return;
	if(sum + fact[curIndex] == n){
		ans = true;
		return;
	}
	DFS(curIndex+1,sum + fact[curIndex]);
	DFS(curIndex+1,sum);
}

int main() {
	scanf("%d",&n);

	fact[0] = 1;
	while(maxIndex < M && fact[maxIndex] <= n) {
		maxIndex++;
		fact[maxIndex] = fact[maxIndex-1] * maxIndex;
	}
	DFS(0,0);
	char str[5];
	if(ans)
		strcpy(str,"YES");
	else
		strcpy(str,"NO");
	printf("%s",str);
	return 0;
}

#include <stdio.h>
(737)#include <string.h>

const int N = 1000000;
const int M = 11;
int n;
int fact[M];
int maxIndex = 0;
bool dp[N];
bool ans = false;


void bag() {
	dp[0] = true;
	for(int i = 0; i <= maxIndex; i++) 
		for(int j = n; j >= fact[i]; j--) 
			if(dp[j] == true || dp[j - fact[i]] == true)
				dp[j] =true;
}

int main() {
	scanf("%d",&n);
	fact[0] = 1;
	while(maxIndex < M && fact[maxIndex] <= n) {
		maxIndex++;
		fact[maxIndex] = fact[maxIndex-1] * maxIndex;
	}
	bag();
	ans = dp[n];
	char str[5];
	if(ans)
		strcpy(str,"YES");
	else
		strcpy(str,"NO");
	printf("%s",str);
	return 0;
}

#include <iostream>
#include<vector>
using namespace std;

int main() {
//这里其实是使用的是暴力搜索，先创建一个数组用来存储1-10的阶乘的结果，
//由于10！已经是大于1000000了，因此其已经够对于n的值的搜索

//这里注意0!=1,这里是可以使用的如：4=0！+1！+2！，因此输出为YES

    vector<int>dp(11);
    dp[0] = 1;
    for (int i = 1; i <= 10; i++) {
        dp[i] = dp[i - 1] * i;
    }
    int n;
    while (cin >> n) {
        for (int i = 10; i >= 0; i--) {
            if (n >= dp[i])
                n = n - dp[i];
            if (n == 0) {
                cout << "YES" << endl;
                break;
            }
        }
        if (n != 0)cout << "NO" << endl;
    }
}

#include <iostream>
using namespace std;

int factorial(int n) {  //求阶乘
    return n <= 1 ? 1 : n * factorial(n - 1);
}

int main() {
    int n;
    while (cin >> n) {
        for (int i = 9; i >= 0; i--) {
            int factorial_i = factorial(i);
            if (n >= factorial_i) {
                n -= factorial_i;
            }
        }
        cout << (n == 0 ? "YES" : "NO") << endl;
    }
    return 0;
}

两个DP思路：
1、n是否可以表示。拆解为n-x是否可以表示，但会出现阶乘重复使用的问题。
2、每个数选或不选，即0-1背包问题。
提前计算出所有<=n的阶乘。问题转化为从一个有序数组中找出若干个，每个只能用一次，使其和等于一个特定数。每个数有选和不选两种状态，这就是经典的0-1背包问题。本题还可以做空间优化。

#include <cstdio>
(802)#include <vector>

using namespace std;

int main(){
    int n, temp=1, x=1;
    scanf("%d", &n);
    vector<int> fac;
    while(temp<=n){
        fac.emplace_back(temp);
        temp *= x;
        x++;
    }
    int m = x-1;
    bool dp[n+1]={};
    dp[0] = true;
    for(int k=1; k<=m; k++){
        for(int t=n; t>=0; t--){
            dp[t] = t>=fac[k-1] ? (dp[t] || dp[t-fac[k-1]]) : dp[t];
        }
    }
    if(dp[n]) printf("YES");
    else printf("NO");
    return 0;
}

//注意4也是可以的，因为0！+1！+2！=4，即不要忘了0的阶乘 
#include<iostream>
using namespace std;

int result(int x){
	if(x==0)
		return 1;
	else
		return x*result(x-1);	
}

int main(){
	int n,i,a[10],temp;
	for(i=0;i<=9;i++)
		a[i]=result(i);
	while(cin>>n){
		int sum=n;
		int flag=1;
		for(i=0;i<=9;i++)
			if(a[i]>n){
				temp=i;	
				break;
			}
		for(i=temp-1;i>=0;i--){
			if(sum-a[i]<0)
				continue;
			sum=sum-a[i];
			if(sum==0){
				cout<<"YES"<<endl;
				flag=0;
				break;
			}	
		}
		if(flag==1)
			cout<<"NO"<<endl;
	}
	return 0;
}