結果
| 問題 | No.420 mod2漸化式 |
| ユーザー |
👑  emthrm
|
| 提出日時 | 2020-03-15 21:23:36 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 22 ms / 1,000 ms |
| コード長 | 10,865 bytes |
| コンパイル時間 | 3,248 ms |
| コンパイル使用メモリ | 222,316 KB |
| 最終ジャッジ日時 | 2025-01-09 07:08:01 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 35 |
ソースコード
#define _USE_MATH_DEFINES#include <bits/stdc++.h>using namespace std;#define FOR(i,m,n) for(int i=(m);i<(n);++i)#define REP(i,n) FOR(i,0,n)#define ALL(v) (v).begin(),(v).end()using ll = long long;const int INF = 0x3f3f3f3f;const ll LINF = 0x3f3f3f3f3f3f3f3fLL;const double EPS = 1e-8;const int MOD = 1000000007;// const int MOD = 998244353;const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};const int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }struct IOSetup {IOSetup() {cin.tie(nullptr);ios_base::sync_with_stdio(false);cout << fixed << setprecision(20);}} iosetup;const int LG10_BASE = 9, BASE = 1000000000; // BASE = 10^{LG_10BASE}struct BigInt {int sign; vector<int> dat;BigInt(ll val = 0) { *this = val; }BigInt(const string &s) { *this = s; }vector<ll> convert_base(int new_lg10_base, int new_base) const {// assert(new_base == static_cast<int>(round(pow(10, new_lg10_base))));int mx_base = max(LG10_BASE, new_lg10_base);vector<ll> p(mx_base + 1, 1);FOR(i, 1, mx_base + 1) p[i] = p[i - 1] * 10;vector<ll> res;ll now_val = 0;int now_lg10_base = 0;for (int e : dat) {now_val += p[now_lg10_base] * e;now_lg10_base += LG10_BASE;while (now_lg10_base >= new_lg10_base) {res.emplace_back(now_val % new_base);now_val /= new_base;now_lg10_base -= new_lg10_base;}}res.emplace_back(now_val);while (!res.empty() && res.back() == 0) res.pop_back();return res;}int digit_sum() {assert(sign == 1);string s = to_string();int res = 0;for (char c : s) res += c - '0';return res;}int length() {if (dat.empty()) return 0;int res = LG10_BASE * (dat.size() - 1);int tmp = dat.back();while (tmp > 0) { ++res; tmp /= 10; }return res;}BigInt pow(BigInt exponent) {BigInt res = 1, tmp = *this;while (exponent > 0) {if (exponent.dat[0] & 1) res *= tmp;tmp *= tmp;exponent /= 2;}return res;}ll to_llong() const {assert(*this >= LLONG_MIN && *this <= LLONG_MAX);ll res = 0;for (int i = static_cast<int>(dat.size()) - 1; i >= 0; --i) (res *= BASE) += dat[i];return res;}string to_string() { stringstream ss; ss << *this; string res; ss >> res; return res; }void trim() {while (!dat.empty() && dat.back() == 0) dat.pop_back();if (dat.empty()) sign = 1;}BigInt &operator=(ll val) {sign = 1;if (val < 0) { sign = -1; val = -val;}dat.clear();for (; val > 0; val /= BASE) dat.emplace_back(val % BASE);return *this;}BigInt &operator=(const string &s) {sign = 1;dat.clear();if (!s.empty()) {int tail = 0;if (s[tail] == '-' || s[tail] == '+') {if (s[tail] == '-') sign = -1;++tail;}for (int i = s.length() - 1; i >= tail; i -= LG10_BASE) {int val = 0;for (int j = max(tail, i - LG10_BASE + 1); j <= i; ++j) val = val * 10 + (s[j] - '0');dat.emplace_back(val);}}trim();return *this;}BigInt &operator=(const BigInt &x) {sign = x.sign;dat.resize(x.dat.size());copy(ALL(x.dat), dat.begin());return *this;}BigInt &operator+=(const BigInt &x) {if (sign == x.sign) {bool carry = false;for (int i = 0; i < max(dat.size(), x.dat.size()) || carry; ++i) {if (i == dat.size()) dat.emplace_back(0);dat[i] += (i < x.dat.size() ? x.dat[i] : 0) + carry;carry = dat[i] >= BASE;if (carry) dat[i] -= BASE;}} else {*this -= -x;}return *this;}BigInt &operator-=(const BigInt &x) {if (sign == x.sign) {BigInt abs_this = *this, abs_x = x;abs_this.sign = 1; abs_x.sign = 1;if (abs_this >= abs_x) {bool carry = false;for (int i = 0; i < dat.size() || carry; ++i) {dat[i] -= (i < x.dat.size() ? x.dat[i] : 0) + carry;carry = dat[i] < 0;if (carry) dat[i] += BASE;}trim();} else {*this = -(x - *this);}} else {*this += -x;}return *this;}BigInt &operator*=(const BigInt &x) {const int new_log10_base = 6, new_base = 1000000;vector<ll> this6 = convert_base(new_log10_base, new_base), x6 = x.convert_base(new_log10_base, new_base);vector<ll> res = karatsuba(this6, 0, this6.size(), x6, 0, x6.size());REP(i, res.size()) {ll quo = res[i] / new_base;if (quo > 0) {if (i + 1 == res.size()) res.emplace_back(0);res[i + 1] += quo;}res[i] %= new_base;}string s = (sign * x.sign == 1 ? "+" : "-");for (int i = static_cast<int>(res.size()) - 1; i >= 0; --i) {string tmp = std::to_string(res[i]);REP(_, new_log10_base - tmp.size()) s += '0';s += tmp;}return *this = s;}BigInt &operator/=(int x) { return *this = divide(x).first; }BigInt &operator/=(const BigInt &x) { return *this = divide(x).first; }BigInt &operator%=(int x) { return *this = divide(x).second; }BigInt &operator%=(const BigInt &x) { return *this = divide(x).second; }bool operator==(const BigInt &x) const {if (sign != x.sign || dat.size() != x.dat.size()) return false;int sz = dat.size();REP(i, sz) if (dat[i] != x.dat[i]) return false;return true;}bool operator!=(const BigInt &x) const { return !(*this == x); }bool operator<(const BigInt &x) const {if (sign != x.sign) return sign < x.sign;if (dat.size() != x.dat.size()) return sign * dat.size() < x.sign * x.dat.size();for (int i = static_cast<int>(dat.size()) - 1; i >= 0; --i) {if (dat[i] != x.dat[i]) return dat[i] * sign < x.dat[i] * x.sign;}return false;}bool operator<=(const BigInt &x) const { return !(x < *this); }bool operator>(const BigInt &x) const { return x < *this; }bool operator>=(const BigInt &x) const { return !(*this < x); }BigInt &operator++() { return *this += 1; }BigInt operator++(int) { BigInt res = *this; ++*this; return res; }BigInt &operator--() { return *this -= 1; }BigInt operator--(int) { BigInt res = *this; --*this; return res; }BigInt operator+() const { return *this; }BigInt operator-() const { BigInt res = *this; res.sign = -res.sign; return res; }BigInt operator+(const BigInt &x) const { return BigInt(*this) += x; }BigInt operator-(const BigInt &x) const { return BigInt(*this) -= x; }BigInt operator*(const BigInt &x) const { return BigInt(*this) *= x; }BigInt operator/(int x) const { return BigInt(*this) /= x; }BigInt operator/(const BigInt &x) const { return BigInt(*this) /= x; }BigInt operator%(int x) const { return BigInt(*this) %= x; }BigInt operator%(const BigInt &x) const { return BigInt(*this) %= x; }friend ostream &operator<<(ostream &os, const BigInt &x) {if (x.sign == -1) os << '-';os << (x.dat.empty() ? 0 : x.dat.back());for (int i = static_cast<int>(x.dat.size()) - 2; i >= 0; --i) os << setw(LG10_BASE) << setfill('0') << x.dat[i];return os;}friend istream &operator>>(istream &is, BigInt &x) { string s; is >> s; x = s; return is; }private:vector<ll> karatsuba(vector<ll> &a, int a_l, int a_r, vector<ll> &b, int b_l, int b_r) {int a_len = a_r - a_l, b_len = b_r - b_l;if (a_len < b_len) return karatsuba(b, b_l, b_r, a, a_l, a_r);vector<ll> res(a_len + b_len, 0);if (b_len <= 32) {FOR(i, a_l, a_r) FOR(j, b_l, b_r) res[(i - a_l) + (j - b_l)] += a[i] * b[j];} else {int mid = (a_len + 1) / 2, n = min(a_len, mid);for (int i = a_l; i + mid < a_r; ++i) a[i] += a[i + mid];for (int i = b_l; i + mid < b_r; ++i) b[i] += b[i + mid];vector<ll> tmp = karatsuba(a, a_l, a_l + mid, b, b_l, b_l + n);REP(i, tmp.size()) res[mid + i] = tmp[i];for (int i = a_l; i + mid < a_r; ++i) a[i] -= a[i + mid];for (int i = b_l; i + mid < b_r; ++i) b[i] -= b[i + mid];tmp = karatsuba(a, a_l, a_l + mid, b, b_l, b_l + n);REP(i, tmp.size()) { res[i] += tmp[i]; res[mid + i] -= tmp[i]; }tmp = karatsuba(a, a_l + mid, a_r, b, b_l + n, b_r);REP(i, tmp.size()) { res[mid + i] -= tmp[i]; res[(mid << 1) + i] += tmp[i]; }}while (!res.empty() && res.back() == 0) res.pop_back();return res;}pair<BigInt, int> divide(int x) {// assert(!x.dat.empty());BigInt dividend = *this;if (x < 0) { dividend.sign = -dividend.sign; x = -x; }ll rem = 0;for (int i = static_cast<int>(dividend.dat.size()) - 1; i >= 0; --i) {ll tmp = rem * BASE + dividend.dat[i];dividend.dat[i] = static_cast<int>(tmp / x);rem = tmp % x;}dividend.trim();return {dividend, static_cast<int>(rem)};}pair<BigInt, BigInt> divide(const BigInt &x) {// assert(!x.dat.empty());int k = BASE / (x.dat.back() + 1);BigInt dividend = *this, divisor = x;dividend.sign = 1; divisor.sign = 1;dividend *= k; divisor *= k;BigInt quo, rem = 0;quo.dat.resize(dividend.dat.size());int sz = divisor.dat.size();for (int i = static_cast<int>(dividend.dat.size()) - 1; i >= 0; --i) {rem.dat.insert(rem.dat.begin(), dividend.dat[i]);quo.dat[i] = static_cast<int>(((sz < rem.dat.size() ? 1LL * rem.dat[sz] * BASE : 0) + (sz - 1 < rem.dat.size() ? rem.dat[sz - 1] : 0)) /divisor.dat.back());rem -= divisor * quo.dat[i];while (rem.sign == -1) { rem += divisor; --quo.dat[i]; }}quo.sign = sign * x.sign; rem.sign = sign;quo.trim(); rem.trim();return {quo, rem / k};}};BigInt __gcd(BigInt a, BigInt b) { while (!b.dat.empty()) swap(a %= b, b); return a; }BigInt __lcm(const BigInt &a, const BigInt &b) { return a / __gcd(a, b) * b; }BigInt abs(const BigInt &x) { BigInt res = x; res.sign = 1; return res; }BigInt max(const BigInt &a, const BigInt &b) { return a < b ? b : a; }BigInt min(const BigInt &a, const BigInt &b) { return a < b ? a : b; }template <typename T>vector<vector<T> > pascal(int val) {vector<vector<T> > c(val + 1, vector<T>(val + 1, 0));REP(i, val + 1) {c[i][0] = 1;FOR(j, 1, i + 1) c[i][j] = c[i - 1][j - 1] + c[i - 1][j];}return c;}int main() {const int N = 31;vector<vector<BigInt> > c = pascal<BigInt>(N);int x; cin >> x;if (x > N) {cout << "0 0\n";return 0;}cout << c[N][x] << ' ';BigInt ans = 0;if (x > 0) {REP(bit, N) ans += c[N - 1][x - 1] * (1 << bit);}cout << ans << '\n';return 0;}