阶乘之和 题解

题目大意

求正整数 $n$ 是否能分解为若干个阶乘之和

思路分析

直接暴力枚举。枚举10种状态，每种为选或不选。

代码

#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define IL inline
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;

int a[12] = {0,1,1,2,6,24,120,720,5040,40320,362880};
bool used[11];

bool f(int q)
{
	if(q == 0 || q > 409114) // 特判为0或超出范围
		return false;
    //枚举10种状态，每种为选或不选。
	for(int a1 = 0;a1 <= 1;a1++)
		for(int a2 = 0;a2 <= 1;a2++)
			for(int a3 = 0;a3 <= 1;a3++)
				for(int a4 = 0;a4 <= 1;a4++)
					for(int a5 = 0;a5 <= 1;a5++)
						for(int a6 = 0;a6 <= 1;a6++)
							for(int a7 = 0;a7 <= 1;a7++)
								for(int a8 = 0;a8 <= 1;a8++)
									for(int a9 = 0;a9 <= 1;a9++)
										for(int a10 = 0;a10 <= 1;a10++)
												if(q == (a1*a[1] +a2*a[2] +a3*a[3] +a4*a[4] +a5*a[5] +a6*a[6] +a7*a[7] +a8*a[8] +a9*a[9] +a10*a[10]))
													return true;
	return false;
}


int main()
{
	int x;
	while(cin >> x && x >= 0)
	{
		f(x)?puts("YES"):puts("NO");
	}
    return 0;
}

/***************************************
Note:
***************************************/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <iomanip>
#include <cmath>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#include <fstream>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define ULLI unsigned long long int
const int N = 1e6+6;
int n;
bool flag = 0;
int a[10] = {1,1,2,6,24,120,720,5040,40320,362880,3628800};
void dfs(int sum,int step){
	if (sum > n) return;
	if (sum == n) flag = 1;
	if (step > 10) return;
	dfs(sum+a[step],step+1);
	dfs(sum,step+1);
}
int main(){
	while (cin >> n and n >= 0){
        if (n == 0){
            cout << "NO" << endl;
            continue;
        }
		dfs(0,0);
		if (flag) cout << "YES";
		else cout << "NO";
		cout << endl;
		flag = 0;
	}
    return 0;
}