题目描述

给定一个非负整数 n，请你判断是否存在一些整数 xi，能够使得 n=∑1≤i≤txi!，其中 t≥1,xi≥0,xi=xj iff i=j。
iff 表示当且仅当。

输入格式

输入包含多组测试数据。
每组数据占一行，包含一个非负整数 n。
最后一行是一个负数，表示输入结束，无需处理。

输出格式

每组数据输出一行结果，如果 n 能表示为若干数的阶乘之和，则输出 YES，否则输出 NO。

数据范围

0≤n≤106,
每组输入最多包含 100 组数据。

输入样例：

9
-1

输出样例：

YES

解法

这道题目数据范围明确给定了小于1e6，那么最多我们就只能取到9的阶乘，因为10！= 3628800。因此，我们所有能组成的n是由0！~9！这些数值组成的集合。那么总共是10个数，不能不取数，因此总共是2^{10}-1种情况，我们可以利用二进制来枚举所有的情况，一个10位的二进制数，哪一位是1就取得对应的阶乘值，存入哈希表即可！

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
using namespace std;

unordered_set<int> hashtable;

int f[10];

int main()
{
    //预处理出0-9的阶乘能凑出的所有情况
    for(int i = 0; i<=9; i++)
    {
        f[i] = 1;
        for(int j = 1; j<=i; j++)
            f[i] *= j;
    }
    for(int i = 1; i<(1<<10); i++)
    {
        int cur = 0;
        for(int j = 0; j<10; j++)
            if(i>>j & 1)
                cur += f[j];
        hashtable.insert(cur);
    }
    int n;
    while(cin>>n, n>=0)
    {
        if(hashtable.find(n) == hashtable.end()) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}