【題解】ZeroJudge d443: 10497 – Sweet Child Makes Trouble

【範例】大數 BigInteger
【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d443
【解題想法】遞迴、DP、大數

  • 輸入一個數 N (N <= 800),數字1 ~ N 依序排列。任選一個數字P,把 P 改置於數字Q (Q != P)的位置,
    • 如果P與Q剛好互換位置,則可能的組合數同(N-2)個數字的答案。
    • 如果Q不在P原來的位置上,則可能的組合數同(N-1)個數字的答案。
    • 因為P可以放的位置有(N-1)個,所以答案 f(N) = (N-1) * ( f(N-1) + f(N-2) )。
  • N = 800 時,答案有1977個位數,需進行大數計算。
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 2000;

struct BigNum{
    int len;
    int num[maxn];
    
    BigNum(){
        len = 0;
        memset(num, 0, sizeof(num));
    }
    
    void delZero(){
        while (len && num[len-1] == 0){
            len--;
        }
        if (len == 0) {
            num[len++] = 0;
        }
    }
    
    void operator = (int x){
        len = 0;
        while (x){
            num[len++] = x % 10;
            x /= 10;
        }
        delZero();
    }
    
    BigNum operator + (const BigNum& y){
        BigNum ret;
        int carry = 0;
        for (int i = 0; i < len || i < y.len; i++){
            if (i < len) carry += num[i];
            if (i < y.len) carry += y.num[i];
            ret.num[ret.len++] = carry % 10;
            carry /= 10;
        }
        while (carry){
            ret.num[ret.len++] = carry % 10;
            carry /= 10;
        }
        return ret;
    }
    
    BigNum operator * (const int& y){
        BigNum ret;
        int carry = 0;
        for (int i = 0; i < len; i++){
            carry += y * num[i];
            ret.num[ret.len++] = carry % 10;
            carry /= 10;
        }
        while (carry){
            ret.num[ret.len++] = carry % 10;
            carry /= 10;
        }
        return ret;
    }
};

BigNum dp[801];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    dp[0] = 1;
    dp[1] = 0;
    for (int i = 2; i < 801; i++){
        dp[i] = (dp[i-1] + dp[i-2]) * (i-1);
    }
    int N;
    while (cin >> N && N != -1){
        for (int i = dp[N].len-1; i >= 0; i--){
            cout << dp[N].num[i];
        }
        cout << "\n";
    }
    return 0;
}
分享本文 Share with friends