题解 | #Sum of Factorials#

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

int fac[10];//由于n<=1e6,故分解出的factorial一定<=9  (9!=326880,10!=3628800)
unordered_set<int> S;

int main(){
    fac[0] = fac[1] = 1;
    for(int i=2;i<10;i++) fac[i] = fac[i-1]*i;//先算出十个数的阶乘
    //然后就是枚举这十个数0~9,可以暴搜，这里用位运算枚举
    //十位二进制表示选取结果，第i位为1表示选i，把可以凑出的数加入哈希表
    for(int i=1;i<1<<10;i++){
        int s = 0;
        for(int j=0;j<10;j++){
            if(i>>j&1) s+=fac[j];
        S.insert(s);
        }
    }
    int x;
    while(cin>>x) if(S.count(x)) puts("YES"); else puts("NO");
    return 0;
}