205. 数列项

class BigUint {
  public:
    BigUint() {}
    BigUint(u32 num) {
        while (num) {
            auto const [quot, rem] = div(num, 10);
            digits_.push_back(rem);
            num = quot;
        }
    }

    BigUint operator-(BigUint const &rhs) const {
        assert(digits_.size() >= rhs.digits_.size());
        auto ret = digits_;
        for (u32 i = 0, sz = rhs.digits_.size(); i != sz; ++i) {
            ret[i] -= rhs.digits_[i];
            if (ret[i] < 0) {
                ret[i] += 10;
                --ret[i + 1];
            }
        }
        for (u32 i = rhs.digits_.size(); ret[i] < 0;) {
            ret[i] += 10;
            --ret[++i];
        }
        trunc_zero(ret);
        return {move(ret)};
    }

    BigUint operator+(BigUint const &rhs) const {
        if (digits_.size() < rhs.digits_.size()) {
            return rhs + *this;
        }
        auto ret = digits_;
        ret.push_back(0);
        for (u32 i = 0, sz = rhs.digits_.size(); i != sz; ++i) {
            ret[i] += rhs.digits_[i];
            if (ret[i] >= 10) {
                ret[i] -= 10;
                ++ret[i + 1];
            }
        }
        for (u32 i = rhs.digits_.size(); ret[i] >= 10; ++i) {
            ++ret[i + 1];
            ret[i] -= 10;
        }
        trunc_zero(ret);
        return {move(ret)};
    }

    friend ostream &operator<<(ostream &os, BigUint const &num) {
        if (num.digits_.empty()) {
            return os << '0';
        }
        auto i = num.digits_.rbegin();
        auto ed = num.digits_.rend();
        while (i != ed) {
            os << +*i++;
        }
        return os;
    }

  private:
    using DigitVec = vector<i8>;
    DigitVec digits_;

    BigUint(DigitVec &&digits) : digits_(digits) {}

    void static trunc_zero(DigitVec &vec) {
        while (!vec.empty() && vec.back() == 0) {
            vec.pop_back();
        }
    }
};

int main() {
    BigUint arr[102]{0, 0, 1, 1}; // Start from one.
    u32 k, n;
    cin >> k >> n;
    for (u32 i = 4; i <= k; ++i)
        arr[i] = arr[i - 1] + arr[i - 1];
    for (u32 i = max((u32)4, k + 1); i <= n; ++i)
        arr[i] = arr[i - 1] + arr[i - 1] - arr[i - 1 - k];
    cout << arr[n] << '\n';
}