AtCoder Typical Contest 001

Submission #6903962

Source codeソースコード

#include <assert.h>
#include <limits.h>
#include <cmath>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <complex>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using ll = long long;
using P = std::pair<ll, ll>;

#define rep(i, a, b) for (ll(i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(i) std::cout << i << "\n"

//const ll MOD = 998244353;
const ll MOD = 1e9+7;

//原始根を使うFFT 法をとっていることに注意
//max_dには多項式2つの次数の積より大きい2^nを渡す
template<ll modu,ll root>
struct NumberTheoreticTransform {
  /*
   modとrootと次数の最大値の組
   1224736769 , 3 , 2^24
   998244353 , 3 , 2^23
  */

 
  ll pow_mod(ll a, ll b, ll mod) {
    if (a % mod == 0) {
      return 0;
    }

    ll x = 1;

    while (b > 0) {
      if (b & 1) {
        x = (x * a) % mod;
      }
      a = (a * a) % mod;
      b >>= 1;
    }
    return x;
  }

  std::vector<ll> zeta,temp;
  ll size=1;

  std::vector<ll> fft(std::vector<ll>& a,bool inv=false){
    ll mask=size-1;
    ll p=0;
    for(ll i=size>>1;i>=1;i>>=1){
      auto& cur=(p&1)?temp:a;
      auto& nex = (p&1)?a:temp;
      ll e=zeta[inv?(size-i)%size:i];
      ll w=1;
      for(ll j=0;j<size;j+=i){
        for(ll k=0;k<i;k++){
          nex[j+k]=(cur[((j<<1)&mask)+k]+w*cur[(((j<<1)+i)&mask)+k])%modu;
        }
        w=(w*e)%modu;
      }
      p++;
    }
    if(p&1)std::swap(a,temp);
    if(inv)for(ll i=0;i<size;i++)a[i]=(a[i]*pow_mod(size,modu-2,modu))%modu;
    return a;
  }

  std::vector<ll> mul(std::vector<ll>& a,std::vector<ll>& b){
    ll m=a.size()+b.size()-1;
    size=1;
    while(m>size){size<<=1;}
    ll ze=pow_mod(root,(modu-1)/size,modu);
    temp.resize(size);
    zeta.resize(size);
    zeta[0]=1;
    for(ll i=1;i<size;i++)zeta[i]=(zeta[i-1]*ze)%modu;
    std::vector<ll> A(size),B(size);
    for(ll i=0;i<a.size();i++)A[i]=a[i];
    for(ll i=0;i<b.size();i++)B[i]=b[i];

    A=fft(A);B=fft(B);
    for(ll i=0;i<size;i++)A[i]=(A[i]*B[i])%modu;
    A=fft(A,true);
    A.resize(m);
    return A;
  }

};
 
int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  //問題文中の添え字が0-indexか1-indexか確認!

  ll n;
  std::cin>>n;
  std::vector<ll> a(n+1),b(n+1);
  a[0]=0;b[0]=0;
  rep(i,0,n){
    ll x,y;
    std::cin>>x>>y;
    a[i+1]=x;b[i+1]=y;
  }

  NumberTheoreticTransform<1224736769,3> ntt;

  std::vector<ll> c=ntt.mul(a,b);

  rep(i,1,2*n+1)std::cout<<c[i]<<"\n";
  return 0;
}

Submission

Task問題 C - 高速フーリエ変換
User nameユーザ名 Imperi
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 2745 Byte
File nameファイル名
Exec time実行時間 111 ms
Memory usageメモリ使用量 12032 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - 00_sample_01
All 100 / 100 00_sample_01,01_00_01,01_01_19,01_02_31,01_03_22,01_04_31,01_05_40,01_06_15,01_07_39,01_08_28,01_09_30,01_10_23,01_11_33,01_12_11,01_13_28,01_14_41,01_15_26,01_16_49,01_17_34,01_18_02,01_19_33,01_20_29,02_00_51254,02_01_82431,02_02_17056,02_03_34866,02_04_6779,02_05_65534,02_06_65535,02_07_65536,02_08_65537,02_09_65538,02_10_100000

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_sample_01 AC 1 ms 256 KB
01_00_01 AC 1 ms 256 KB
01_01_19 AC 1 ms 256 KB
01_02_31 AC 1 ms 256 KB
01_03_22 AC 1 ms 256 KB
01_04_31 AC 1 ms 256 KB
01_05_40 AC 1 ms 256 KB
01_06_15 AC 1 ms 256 KB
01_07_39 AC 1 ms 256 KB
01_08_28 AC 1 ms 256 KB
01_09_30 AC 1 ms 256 KB
01_10_23 AC 1 ms 256 KB
01_11_33 AC 1 ms 256 KB
01_12_11 AC 1 ms 256 KB
01_13_28 AC 1 ms 256 KB
01_14_41 AC 1 ms 256 KB
01_15_26 AC 1 ms 256 KB
01_16_49 AC 1 ms 256 KB
01_17_34 AC 1 ms 256 KB
01_18_02 AC 1 ms 256 KB
01_19_33 AC 1 ms 256 KB
01_20_29 AC 1 ms 256 KB
02_00_51254 AC 57 ms 6272 KB
02_01_82431 AC 109 ms 11776 KB
02_02_17056 AC 26 ms 3072 KB
02_03_34866 AC 51 ms 6016 KB
02_04_6779 AC 8 ms 1024 KB
02_05_65534 AC 59 ms 6644 KB
02_06_65535 AC 59 ms 6644 KB
02_07_65536 AC 101 ms 11520 KB
02_08_65537 AC 101 ms 11520 KB
02_09_65538 AC 101 ms 11520 KB
02_10_100000 AC 111 ms 12032 KB