結果

問題 No.303 割れません
ユーザー mamekin
提出日時 2016-01-30 17:03:32
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
MLE  
実行時間 -
コード長 4,986 bytes
コンパイル時間 986 ms
コンパイル使用メモリ 104,280 KB
実行使用メモリ 814,676 KB
最終ジャッジ日時 2024-09-21 19:26:02
合計ジャッジ時間 4,227 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other MLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

class Bigint
{
    static const long long MAX = 1000000000LL;
    vector<long long> a;
    bool sign;
public:
    Bigint(){
        sign = true;
    }
    Bigint(long long x){
        if(x < 0){
            sign = false;
            x *= -1;
        }
        else{
            sign = true;
        }
        while(x > 0){
            a.push_back(x % MAX);
            x /= MAX;
        }
    }
    Bigint(const string& s){
        sign = true;
        long long tmp = MAX;
        for(int i=s.size()-1; i>=0; --i){
            if(tmp == MAX){
                a.push_back(0);
                tmp = 1;
            }
            if('0' <= s[i] && s[i] <= '9'){
                a.back() += (s[i] - '0') * tmp;
                tmp *= 10;
            }
            else if(i == 0 && s[0] == '-'){
                sign = false;
            }
            else{
                throw(exception());
            }
        }
        while(!a.empty() && a.back() == 0)
            a.pop_back();
        if(a.empty())
            sign = true;
    }
    long long getNum(){
        long long ret = 0;
        for(int i=a.size()-1; i>=0; --i){
            ret *= MAX;
            ret += a[i];
        }
        return ret * (sign? 1:-1);
    }
    string getStr() const{
        ostringstream oss;
        if(a.size() == 0)
            return "0";
        if(!sign)
            oss << '-';
        for(int i=a.size()-1; i>=0; --i){
            oss << a[i];
            oss << setw(9) << setfill('0');
        }
        return oss.str();
    }
    Bigint operator+(const Bigint& x) const{
        if(sign ^ x.sign){
            Bigint tmp = x;
            tmp.sign = !tmp.sign;
            return *this - tmp;
        }
        Bigint ret;
        ret.sign = sign;
        long long carry = 0;
        unsigned i = 0;
        while(i < a.size() || i < x.a.size() || carry > 0){
            if(i < a.size())
                carry += a[i];
            if(i < x.a.size())
                carry += x.a[i];
            ret.a.push_back(carry % MAX);
            carry /= MAX;
            ++ i;
        }
        return ret;
    }
    Bigint operator-(const Bigint& x) const{
        if(sign ^ x.sign){
            Bigint tmp = x;
            tmp.sign = !tmp.sign;
            return *this + tmp;
        }
        Bigint ret;
        long long carry = 0;
        unsigned i=0;
        while(i < a.size() || i < x.a.size()){
            if(i < a.size())
                carry += a[i];
            if(i < x.a.size())
                carry -= x.a[i];
            if(carry < 0){
                ret.a.push_back(MAX + carry);
                carry = -1;
            }
            else{
                ret.a.push_back(carry);
                carry = 0;
            }
            ++ i;
        }
        if(carry == -1){
            ret.sign = !ret.sign;
            for(unsigned j=0; j<ret.a.size(); ++j)
                ret.a[j] = MAX - ret.a[j] - 1;
            ++ ret.a[0];
        }
        while(!ret.a.empty() && ret.a.back() == 0)
            ret.a.pop_back();
        return ret;
    }
    Bigint operator*(const Bigint& x) const{
        if(a.size() == 0 || x.a.size() == 0)
            return 0;
        Bigint ret;
        ret.sign = !(sign ^ x.sign);
        ret.a.assign(a.size() + x.a.size(), 0);
        for(unsigned i=0; i<a.size(); ++i){
            for(unsigned j=0; j<x.a.size(); ++j){
                ret.a[i+j] += a[i] * x.a[j];
                ret.a[i+j+1] += ret.a[i+j] / MAX;
                ret.a[i+j] %= MAX;
            }
        }
        if(!ret.a.empty() && ret.a.back() == 0)
            ret.a.pop_back();
        return ret;
    }
    bool operator<(const Bigint& x) const{
        if(sign ^ x.sign)
            return x.sign;
        if(a.size() != x.a.size())
            return !(sign ^ (a.size() < x.a.size()));
        for(int i=a.size()-1; i>=0; --i){
            if(a[i] != x.a[i])
                return !(sign ^ (a[i] < x.a[i]));
        }
        return false;
    }
};

Bigint solve(int len)
{
    vector<Bigint> dp(len+1, 0);
    vector<Bigint> sum(len+1, 0);
    dp[0] = 1;
    sum[0] = 1;

    for(int i=1; i<=len; ++i){
        dp[i] = dp[i] + sum[i-1];
        sum[i] = dp[i];
        if(i >= 2)
            sum[i] = sum[i] + sum[i-2];
    }

    return dp[len];
}

int main()
{
    int len;
    cin >> len;

    if(len == 2){
        cout << 3 << endl << "INF" << endl;
        return 0;
    }

    Bigint ans = solve(len);
    if(len % 2 == 0){
        Bigint x = solve(len / 2);
        ans = ans - x * x;
    }
    cout << len << endl << ans.getStr() << endl;

    return 0;
}
0