結果

問題 No.723 2つの数の和
ユーザー ineedyourlovep
提出日時 2023-04-27 19:35:41
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 2,663 bytes
コンパイル時間 2,162 ms
コンパイル使用メモリ 203,544 KB
最終ジャッジ日時 2025-02-12 14:26:41
ジャッジサーバーID
（参考情報） 		judge1 / 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;

//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;
  ll x;
  cin >> n >> x;
  vector<ll> a(n);
  rep(i, 0, n) cin >> a[i];
  vector<ll> cnt(100005);
  rep(i, 0, n) cnt[a[i]]++;
  auto c = FFT::multiply(cnt, cnt);
  cout << c[x] << endl;
  return 0;
}
0