POJ 1755 Sum of Factorials 解题报告

一、问题描述

Description

There are some numbers which can be expressed by the sum of factorials. For example 9,9=1!+2!+3! Dr. von Neumann was very interested in such numbers. So, he gives you a number n, and wants you to tell him whether or not the number can be expressed by the sum of some factorials.
Well, it's just a piece of cake. For a given n, you'll check if there are some xi, and let n equal to Σ_1<=i<=tx_i!. (t >=1 1, xi >= 0, xi = xj iff. i = j). If the answer is yes, say "YES"; otherwise, print out "NO".

Input

You will get several non-negative integer n (n <= 1,000,000) from input file. Each one is in a line by itself.
The input is terminated by a line with a negative integer.

Output

For each n, you should print exactly one word ("YES" or "NO") in a single line. No extra spaces are allowed.

Sample Input

9

-1

Sample Output

YES

二、解题思路

因为输入n 最大为1000000，而10！=3628800>1000000，9!=362880，列举出0-9的所有阶乘，即int a[10]={1,1,2,6,24,120,720,5040,40320,362880}，算出这10个数的所有子集和。b[i]表示是否可以组合出数i。

三、代码

 

#include<iostream>
using namespace std;
bool b[1000001];
int sum=0;
int a[10]={1,1,2,6,24,120,720,5040,40320,362880};
void calculate(int n)
{
    if(n>=10)
        return ;
    sum+=a[n];
    b[sum]=true;
    calculate(n+1);
    sum-=a[n];
    calculate(n+1);    
}
int main()
{
    memset(b,0,sizeof(b[0]));
    calculate(0);
    b[0]=false;
    int n;
    cin>>n;
    while( n>=0)
    {
        if(b[n])
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
        cin>>n;
    }
    return 0;
}