Submission #978163


Source Code Expand

#include <cstdio>

int m;
int k;

typedef unsigned Zp;

const int mod = 1224736769;
const Zp root = 3;

Zp A[1<<18];
Zp B[1<<18];
Zp w[1<<17];
Zp y[1<<17];

Zp add(Zp lhs, Zp rhs){
  Zp r = lhs + rhs;
  if(r >= mod) return r - mod;
  else return r;
}

Zp sub(Zp lhs, Zp rhs){
  if(lhs >= rhs) return lhs - rhs;
  else return mod + lhs - rhs;
}

Zp mul(Zp lhs, Zp rhs){
  return ((long long) lhs * rhs) % mod;
}

Zp powr(Zp x, int n){
  Zp r = 1;
  for(; n; n>>=1){
    if(n&0x1) r = mul(r, x);
    x = mul(x, x);
  }
  return r;
}

Zp inv(Zp x){
  return powr(x, mod-2);
}

unsigned clp2(unsigned x) {
   x = x - 1;
   x = x | (x >> 1);
   x = x | (x >> 2);
   x = x | (x >> 4);
   x = x | (x >> 8);
   x = x | (x >>16);
   return x + 1;
}

void fft(Zp *A){
  int u = 1;
  int v = m/2;
  for(int i=k;i>0;i--){
    for(int jh=0;jh<u;jh++){
      Zp wj = w[jh];
      for(int j = jh << i, je = j|v;j<je; j++){
        Zp Ajv = mul(wj, A[j|v]);
        A[j|v]  = sub(A[j], Ajv);
        A[j]   = add(A[j], Ajv);
      }
    }
    u <<= 1;
    v >>= 1;
  }
}

void ifft(Zp *A){
  int u = m/2;
  int v = 1;
  for(int i=1;i<=k;i++){
    for(int jh=0;jh<u;jh++){
      Zp wj = y[jh];
      for(int j = jh << i, je = j|v;j<je; j++){
        Zp Ajv = sub(A[j], A[j|v]);
        A[j] = add(A[j], A[j|v]);
        A[j|v] = mul(wj, Ajv);
      }
    }
    u >>= 1;
    v <<= 1;
  }
}

void genwy(int i, int b, Zp z, Zp x){
  if(b == 0) {
    w[i] = z;
    y[i] = x;
  }
  else {
    genwy(i, b>>1, z, x);
    genwy(i|b, b>>1, mul(z, w[b]), mul(x, y[b]));
  }
}

int main(){
  int n;
  std::scanf("%d", &n);
  for(int i=1;i<=n;i++){
    int a, b;
    std::scanf(" %d %d", &a, &b);
    A[i] = a;
    B[i] = b;
  }
  m = clp2(n+1) << 1;
  k = __builtin_ctz(m);
  Zp z=powr(root, (mod-1)/m);
  Zp x=inv(z);
  for(int j=m/4; j; j>>=1){
    w[j] = z;
    z = mul(z, z);
    y[j] = x;
    x = mul(x, x);
  }
  genwy(0, m/4, 1, 1);
  fft(A);
  fft(B);
  for(int i=0;i<m;i++){
    A[i] = mul(A[i], B[i]);
  }
  ifft(A);
  Zp im = inv(m);
  for(int i=1;i<=2*n;i++){
    std::printf("%d\n", mul(A[i], im));
  }
}

Submission Info

Submission Time
Task C - 高速フーリエ変換
User ryuhei
Language C++ (GCC 4.9.2)
Score 100
Code Size 2219 Byte
Status AC
Exec Time 184 ms
Memory 3748 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:101:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   std::scanf("%d", &n);
                       ^
./Main.cpp:104:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     std::scanf(" %d %d", &a, &b);
                                 ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 1
AC × 33
Set Name Test Cases
Sample 00_sample_01
All 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
Case Name Status Exec Time Memory
00_sample_01 AC 15 ms 800 KB
01_00_01 AC 16 ms 696 KB
01_01_19 AC 16 ms 652 KB
01_02_31 AC 15 ms 800 KB
01_03_22 AC 15 ms 668 KB
01_04_31 AC 18 ms 692 KB
01_05_40 AC 17 ms 792 KB
01_06_15 AC 17 ms 684 KB
01_07_39 AC 17 ms 696 KB
01_08_28 AC 17 ms 800 KB
01_09_30 AC 17 ms 796 KB
01_10_23 AC 16 ms 696 KB
01_11_33 AC 17 ms 684 KB
01_12_11 AC 17 ms 692 KB
01_13_28 AC 17 ms 688 KB
01_14_41 AC 17 ms 700 KB
01_15_26 AC 17 ms 800 KB
01_16_49 AC 17 ms 696 KB
01_17_34 AC 17 ms 792 KB
01_18_02 AC 15 ms 800 KB
01_19_33 AC 17 ms 692 KB
01_20_29 AC 17 ms 796 KB
02_00_51254 AC 97 ms 2212 KB
02_01_82431 AC 163 ms 3748 KB
02_02_17056 AC 47 ms 1568 KB
02_03_34866 AC 80 ms 2204 KB
02_04_6779 AC 27 ms 800 KB
02_05_65534 AC 111 ms 2208 KB
02_06_65535 AC 116 ms 2208 KB
02_07_65536 AC 145 ms 3744 KB
02_08_65537 AC 146 ms 3676 KB
02_09_65538 AC 148 ms 3676 KB
02_10_100000 AC 184 ms 3740 KB