계단의 합(대학원 진학기 시험+01배낭/상압 매거)

원제 링크 사고방식 분석: 원제는 nnn이 몇 개의 곱셈의 합으로 표시될 수 있는지 묻는다. 주의해야 할 것은 0이다!=1 0!=1 0!=1 . 예를 들면 4, 4, 4 하면 0!   +    1 !    + 2 !    0!\;+\;1!\;+2!\; 0!+1!+2! 정확하게 표시하다.각 레벨을 선택하거나 선택하지 않을 수 있음을 발견하여 0101 배낭을 연상합니다.모든 상황을 미리 처리하면 된다.
이외에 선택하거나 선택하지 않는 방안에 대해서는 상압 매거진을 통해 얻을 수 있는 모든 상황.
C o d e : Code: Code:

// 01  
#include 
using namespace std;
typedef long long LL;
const int N = 15, M = 1000010;
LL A[N];
bool dp[M];
signed main(){
     
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    A[0] = 1;
    for(int i = 1; i <= 10; i++){
     
        A[i] = 1ll * A[i-1] * i;
    }
    
    dp[0] = true;
    for(int i = 0; i <= 10; i++){
     
        for(int j = 1000000; j >= A[i]; j--){
     
            dp[j] |= dp[j-A[i]];
        }
    }
    
    LL n;
    while( cin >> n && n >= 0 ){
     
        if( dp[n] && n > 0 ){
     
            cout << "YES" << '
';
        }
        else{
     
            cout << "NO" << '
';
        }
    }
    
    return 0;
}

//    
#include 
using namespace std;
#define MaxN 15
typedef long long LL;
LL A[MaxN];
unordered_set <LL> S;
signed main(){
     
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    A[0] = 1;
    for(int i = 1; i < 10; i++){
     
        A[i] = 1ll * A[i-1] * i;
    }
    
    for(int i = 1; i < 1 << 10; i++){
     
        LL C = 0;
        for(int j = 0; j < 10; j++){
     
            if( i >> j & 1 ){
     
                C += A[j];
            }
        }
        S.insert(C);
    }
    
    LL n;
    while( cin >> n && n >= 0 ){
     
        if( S.count(n) ){
     
            cout << "YES" << '
';
        }
        else{
     
            cout << "NO" << '
';
        }
    }
    
    return 0;
}