結果

問題 No.420 mod2漸化式
ユーザー rsk0315
提出日時 2019-03-28 16:43:27
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,998 bytes
コンパイル時間 573 ms
コンパイル使用メモリ 49,664 KB
最終ジャッジ日時 2025-01-07 00:35:24
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 23 RE * 1 TLE * 11
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:88:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   88 |   scanf("%d", &x);
      |   ~~~~~^~~~~~~~~~

ソースコード

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