阶乘之和 题解

题目大意

求正整数 $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;
}