結果

問題 No.420 mod2漸化式
ユーザー rsk0315rsk0315
提出日時 2019-03-28 16:43:27
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 1,998 bytes
コンパイル時間 580 ms
コンパイル使用メモリ 54,912 KB
実行使用メモリ 13,760 KB
最終ジャッジ日時 2024-04-21 07:21:56
合計ジャッジ時間 3,027 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
13,760 KB
testcase_01 TLE -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstdint>
#include <vector>

template <class Tp>
Tp gcd(Tp a, Tp b, Tp& x, Tp& y) {
  x = Tp(0);
  y = Tp(1);
  for (Tp u=y, v=x; a;) {
    Tp q = b/a;
    std::swap(x-=q*u, u);
    std::swap(y-=q*v, v);
    std::swap(b-=q*a, a);
  }
  return b;
}

template <class Tp>
Tp modinv(Tp a, Tp mod) {
  Tp x, y;
  gcd(a, mod, x, y);
  x %= mod;
  if (x < 0) x += mod;
  return x;
}

template <class Tp>
Tp modadd(Tp a, Tp b, Tp mod) {
  a += b % mod;
  if (a < 0) a += mod;
  if (a >= mod) a -= mod;
  return a;
}

template <class Tp>
Tp modadd(const std::initializer_list<Tp>& adds, Tp mod) {
  Tp res = 0;
  for (const auto& add: adds) {
    res += add % mod;
    if (res < 0) res += mod;
    if (res >= mod) res -= mod;
  }
  return res;
}

template <class Tp>
Tp modsub(Tp a, Tp b, Tp mod) {
  a -= b % mod;
  if (a < 0) a += mod;
  if (a >= mod) a -= mod;
  return a;
}

template <class Tp>
Tp modmul(const std::initializer_list<Tp>& muls, Tp mod) {
  Tp res = 1;
  for (const auto& mul: muls) (res *= mul) %= mod;
  return res;
}

template <class Tp>
class modchoose {
  std::vector<Tp> fact, fact_inv;
  Tp mod;

public:
  modchoose(Tp N, Tp mod): mod(mod) {
    fact.resize(N+1);
    fact_inv.resize(N+1);
    fact[0] = 1;
    for (Tp i = 1; i <= N; ++i)
      fact[i] = fact[i-1] * i % mod;

    fact_inv[N] = modinv(fact[N], mod);
    for (Tp i = N; i--;)
      fact_inv[i] = fact_inv[i+1] * (i+1) % mod;
  }

  Tp operator ()(Tp n, Tp r) const {
    Tp res = fact[n] * fact_inv[r] % mod;
    (res *= fact_inv[n-r]) %= mod;
    return res;
  }
};

int main() {
  int x;
  scanf("%d", &x);
  if (x > 31) return puts("0 0"), 0;

  constexpr intmax_t MOD = 1e9+7;
  modchoose<intmax_t> ncr(32, MOD);

  printf("%jd ", ncr(31, x));

  intmax_t res = 0;
  intmax_t ub = 1L << 31;
  for (intmax_t i = (1L << x) - 1; i < ub;) {
    res += i;

    {
      intmax_t x = i & -i;
      intmax_t y = i + x;
      i = ((i & ~y) / x >> 1) | y;
    }
  }

  printf("%jd\n", res);
}
0