結果

問題 No.723 2つの数の和
コンテスト
ユーザー yuppe19 😺
提出日時 2018-08-06 16:11:13
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 73 ms / 2,000 ms
コード長 3,358 bytes
コンパイル時間 955 ms
コンパイル使用メモリ 90,532 KB
実行使用メモリ 12,392 KB
最終ジャッジ日時 2024-09-19 18:13:01
合計ジャッジ時間 3,394 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cmath>
#include <iostream>
#include <tuple>
#include <vector>
using namespace std;
using i64 = long long;

// {{{ mod_mul, extgcd, mod_inv, mod_pow
inline i64 mod_mul(const i64& x, const i64& y, const i64& m) {
  // yとmの最大ビット長はともに48ビット。
  // http://codeforces.com/blog/entry/15884
  // 12 < floor(63 - log2(MAX_VALUE)) = 15
  // 0xfff = (1<<12) - 1
  i64 b, res = y * (x & 0xfff);
  res += (b=(y<<12) % m) * ((x>>12) & 0xfff);
  res += (b=(b<<12) % m) * ((x>>24) & 0xfff);
  res += (b<<12) % m     * ((x>>36) & 0xfff);
  res %= m;
  return res;
}

inline tuple<i64, i64, i64> extgcd(const i64& x, const i64& y) {
  if(y == 0) { return {1LL, 0LL, x}; }
  i64 a, b, d; tie(a, b, d) = extgcd(y, x%y);
  return {b, a-x/y*b, d};
}

inline i64 mod_inv(const i64& a, const i64& m) {
  i64 x, _, d; tie(x, _, d) = extgcd(a, m);
  return (x % m + m) % m;
}

inline i64 mod_pow(const i64& a, const i64& r, const i64& n, const i64& m) {
  if(n == 0) { return r; }
  if(n & 1)  { return mod_pow(a, mod_mul(a, r, m), n-1, m); }
  return mod_pow(mod_mul(a, a, m), r, n>>1, m);
}

inline i64 mod_pow(const i64 a, const i64 n, const i64 m) {
  return mod_pow(a, 1, n, m);
}
// }}}

struct FMT {
  static vector<i64> convol (const vector<i64>& a, const vector<i64>& b);
  static void        convol2(vector<i64>& a,       vector<i64>& b);       // a に答えが入る。メモリ節約が目的。fftmulで使用。
private:
  static constexpr i64 N = 5LL << 37;
  static constexpr i64 O = 2003LL;
  static constexpr i64 M = N * 211 + 1;
  static void fmt(vector<i64>&);
  static void ifmt(vector<i64>&);
  static void myfmt(vector<i64>&, const bool);
};

// {{{ FMT 実装
void FMT::myfmt(vector<i64> &a, const bool inv) {
  const int n = int(a.size());
  for(int H=1, W=n>>1; H<n; H<<=1, W>>=1) {
    vector<i64> y = a;
    i64 r = mod_pow(O, N/(H*2), M);
    if(inv) { r = mod_inv(r, M); }
    i64 w = 1;
    for(int k=0; k<H; ++k) {
      for(int j=0; j<W; ++j) {
        i64 y0 = y[2*W*k+j],
            y1 = mod_mul(y[2*W*k+j+W], w, M);
        a[W* k   +j] = y0 + y1 < M ? y0 + y1     : y0 + y1 - M;
        a[W*(k+H)+j] = y0 < y1     ? y0 - y1 + M : y0 - y1;
      }
      w = mod_mul(w, r, M);
    }
  }
}

void FMT::fmt(vector<i64> &a) {
  myfmt(a, false);
}

void FMT::ifmt(vector<i64> &a) {
  myfmt(a, true);
  const int n = int(a.size());
  i64 inv = mod_inv(n, M);
  for(int i=0; i<n; ++i) {
    a[i] = mod_mul(a[i], inv, M);
  }
}

vector<i64> FMT::convol(const vector<i64> &a, const vector<i64> &b) {
  int n = 1;
  while(n <= a.size() + b.size()) { n <<= 1; }
  vector<i64> ta = a, tb = b, c(n);
  ta.resize(n);
  tb.resize(n);
  fmt(ta);
  fmt(tb);
  for(int i=0; i<n; ++i) {
    c[i] = mod_mul(ta[i], tb[i], M);
  }
  ifmt(c);
  return c;
}

void FMT::convol2(vector<i64> &a, vector<i64> &b) {
  int n = 1;
  while(n <= a.size() + b.size()) { n <<= 1; }
  a.resize(n);
  b.resize(n);
  fmt(a);
  fmt(b);
  for(int i=0; i<n; ++i) {
    a[i] = mod_mul(a[i], b[i], M);
  }
  ifmt(a);
}
// }}}

constexpr int N = int(powl(10, 5)) + 10;

int main(void) {
  int n; i64 x; scanf("%d%lld", &n, &x);
  vector<i64> a(N);
  for(int i=0; i<n; ++i) {
    int v; scanf("%d", &v);
    ++a[v];
  }
  vector<i64> c = FMT::convol(a, a);
  i64 res = 0;
  if(x < c.size()) {
    res = c[x];
  }
  printf("%lld\n", res);
  return 0;
}
0