結果

問題 No.723 2つの数の和
コンテスト
ユーザー ineedyourlovep
提出日時 2023-04-30 01:16:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 4,968 bytes
コンパイル時間 1,956 ms
コンパイル使用メモリ 205,052 KB
最終ジャッジ日時 2025-02-12 16:09:01
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17 RE * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
//const int mod = 1000000007;
//const int mod = 998244353;

//NNT
template<int mod=1012924417>
struct NTT {
  vector<int> rev, rts;
  int base, max_base, root;
  NTT(): base(1), rev{0, 1}, rts{0, 1} {
    assert(mod >= 3 && mod&1);
    auto tmp = mod-1;
    max_base = 0;
    while (tmp%2 == 0) { tmp >>= 1; max_base++; }
    root = 2;
    while (mod_pow(root, (mod-1)>>1) == 1) root++;
    assert(mod_pow(root, mod-1) == 1);
    root = mod_pow(root, (mod-1)>>max_base);
  }
  inline int mod_pow(int x, int n) {
    int res = 1;
    while (n > 0) {
      if (n&1) res = mul(res, x);
      x = mul(x, x);
      n >>= 1;
    }
    return res;
  }
  inline int inverse(int x) { return mod_pow(x, mod-2); }
  inline unsigned add(unsigned x, unsigned y) {
    x += y;
    if (x >= mod) x -= mod;
    return x;
  }
  inline unsigned mul(unsigned a, unsigned b) {
    return 1ull*a*b%(unsigned long long)mod;
  }
  void ensure_base(int nbase) {
    if (nbase <= base) return;
    rev.resize(1<<nbase);
    rts.resize(1<<nbase);
    for (int i = 0; i < (1<<nbase); i++) rev[i] = (rev[i>>1]>>1)+((i&1)<<(nbase-1));
    assert(nbase <= max_base);
    while (base < nbase) {
      int z = mod_pow(root, 1<<(max_base-1-base));
      for (int i = 1<<(base-1); i < (1<<base); i++) {
        rts[i<<1] = rts[i];
        rts[(i<<1)+1] = mul(rts[i], z);
      }
      base++;
    }
  }
  void ntt(vector<int>& a) {
    const int n = (int)a.size();
    assert((n&(n-1)) == 0);
    int zeros = __builtin_ctz(n);
    ensure_base(zeros);
    int shift = base - zeros;
    for (int i = 0; i < n; i++) if (i < (rev[i]>>shift)) swap(a[i], a[rev[i]>>shift]);
    for (int k = 1; k < n; k <<= 1) {
      for (int i = 0; i < n; i += 2*k) {
        for (int j = 0; j < k; j++) {
          int z = mul(a[i+j+k], rts[j+k]);
          a[i+j+k] = add(a[i+j], mod-z);
          a[i+j] = add(a[i+j], z);
        }
      }
    }
  }
  vector<int> multiply(vector<int> a, vector<int> b) {
    int need = (int)a.size() + (int)b.size() - 1;
    int nbase = 1;
    while ((1<<nbase) < need) nbase++;
    ensure_base(nbase);
    int sz = 1<<nbase;
    a.resize(sz, 0); b.resize(sz, 0);
    ntt(a); ntt(b);
    int inv_sz = inverse(sz);
    for (int i = 0; i < sz; i++) a[i] = mul(a[i], mul(b[i], inv_sz));
    reverse(a.begin()+1, a.end());
    ntt(a);
    a.resize(need);
    return a;
  }
};

//FFT
namespace FFT{
  struct num{
    double x,y;
    num(){x=y=0;}
    num(double x,double y):x(x),y(y){}
  };
  inline num operator+(num a,num b){ return num(a.x+b.x,a.y+b.y);}
  inline num operator-(num a,num b){ return num(a.x-b.x,a.y-b.y);}
  inline num operator*(num a,num b){ return num(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
  inline num conj(num a){ return num(a.x,-a.y);}
  int base=1;
  vector<num> rts={{0,0},{1,0}};
  vector<int> rev={0,1};
  const double PI=acosl(-1.0);
  void ensure_base(int nbase){
    if(nbase<=base) return;
    rev.resize(1<<nbase);
    for(int i=0;i<(1<<nbase);i++) rev[i]=(rev[i>>1]>>1)+((i&1)<<(nbase-1));
    rts.resize(1<<nbase);
    while(base<nbase){
      double angle=2*PI/(1<<(base+1));
      for(int i=1<<(base-1);i<(1<<base);i++){
        rts[i<<1]=rts[i];
        double angle_i=angle*(2*i+1-(1<<base));
        rts[(i<<1)+1]=num(cos(angle_i),sin(angle_i));
      }
      base++;
    }
  }
  void fft(vector<num> &a,int n=-1){
    if(n == -1) n = (int)a.size();
    assert((n&(n-1))==0);
    int zeros=__builtin_ctz(n);
    ensure_base(zeros);
    int shift=base-zeros;
    for(int i=0;i<n;i++) if(i<(rev[i]>>shift)) swap(a[i],a[rev[i]>>shift]);
    for(int k=1;k<n;k<<=1){
      for(int i=0;i<n;i+=2*k){
        for(int j=0;j<k;j++){
          num z=a[i+j+k]*rts[j+k];
          a[i+j+k]=a[i+j]-z;
          a[i+j]=a[i+j]+z;
        }
      }
    }
  }
  vector<num> fa;
  template<typename T>
  vector<long long> multiply(const vector<T> &a,const vector<T> &b){
    int need=(int)a.size()+b.size()-1;
    int nbase=0;
    while((1<<nbase)<need) nbase++;
    ensure_base(nbase);
    int sz=1<<nbase;
    if(sz>(int)fa.size()) fa.resize(sz);
    for(int i=0;i<sz;i++){
      int x=(i<(int)a.size()?a[i]:0);
      int y=(i<(int)b.size()?b[i]:0);
      fa[i]=num(x,y);
    }
    fft(fa,sz);
    num r(0,-0.25/sz);
    for(int i=0;i<=(sz>>1);i++){
      int j=(sz-i)&(sz-1);
      num z=(fa[j]*fa[j]-conj(fa[i]*fa[i]))*r;
      if(i!=j)
        fa[j]=(fa[i]*fa[i]-conj(fa[j]*fa[j]))*r;
      fa[i]=z;
    }
    fft(fa,sz);
    vector<long long> res(need);
    for(int i=0;i<need;i++) res[i]=fa[i].x+0.5;
    return res;
  }
};

int main()
{
  int n, x;
  cin >> n >> x;
  vector<int> a(n);
  rep(i, 0, n) cin >> a[i];
  vector<int> cnt(100005);
  rep(i, 0, n) cnt[a[i]]++;
  NTT<> ntt;
  auto f = FFT::multiply(cnt, cnt);
  cout << f[x] << endl;
  return 0;
}
0