Submission #784255


Source Code Expand

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main {
  private static class Task {
    void solve(FastScanner in, PrintWriter out) {
      int n = in.nextInt();
      long[] a = new long[n + 1];
      long[] b = new long[n + 1];
      for (int i = 0; i < n; i++) {
        a[i + 1] = in.nextInt();
        b[i + 1] = in.nextInt();
      }
      long[] ans = conv(a, b, (int) 1e9 + 7);
      for (int i = 1; i < n * 2 + 1; i++) {
        out.println(ans[i]);
      }
    }
    long[] conv(long[] ina, long[] inb, long mod) {
      long[] a = new long[1 << 18];
      long[] b = new long[1 << 18];
      for (int i = 0; i < ina.length; i++) {
        a[i] = ina[i] % mod;
        b[i] = inb[i] % mod;
      }

      NTT ntt = new NTT(1224736769, 3);
      long[] cs = ntt.convolution(a, b);
      long[] res = new long[ina.length * 2 + 1];
      for (int i = 0; i < res.length; i++) {
        res[i] = cs[i] % mod;
      }
      return res;
    }
  }

  static class NTT {
    long mod, root;
    NTT(long mod, long root) {
      this.mod = mod;
      this.root = root;
    }
    long[] ntt(long[] a, int sign) {
      int n = a.length;
      long base = modpow(root, (mod - 1) / n, mod);
      if (sign == -1) base = modinv(base, mod);
      for (int m = n; m >= 2; m >>>= 1) {
        int mh = m >>> 1;
        long w = 1;
        for (int i = 0; i < mh; i++) {
          for (int j = i; j < n; j += m) {
            int k = j + mh;
            long x = (a[j] - a[k] + mod) % mod;
            a[j] = (a[j] + a[k]) % mod;
            a[k] = w * x % mod;
          }
          w = w * base % mod;
        }
        base = base * base % mod;
      }
      int i = 0;
      for (int j = 1; j < n - 1; j++) {
        for (int k = n >> 1; k > (i ^= k); k >>= 1) ;
        if (j > i) {
          long ai = a[i];
          a[i] = a[j];
          a[j] = ai;
        }
      }
      if (sign == -1) {
        long inv = modinv(n, mod);
        for (int j = 0; j < n; j++) a[j] = a[j] * inv % mod;
      }
      return a;
    }

    long modpow(long a, long b, long mod) {
      long res = 1;
      while (b > 0) {
        if ((b & 1) != 0) res = res * a % mod;
        a = a * a % mod;
        b /= 2;
      }
      return res;
    }
    long modinv(long a, long mod) {
      if (a == 0) return -1;
      if (gcd(a, mod) != 1) return -1;
      return modulo(extgcd(a, mod)[0], mod);
    }
    long modulo(long a, long mod) {
      a %= mod;
      a += mod;
      a %= mod;
      return a;
    }
    long gcd(long x, long y) {
      return y > 0 ? gcd(y, x % y) : x;
    }
    long[] extgcd(long a, long b) {
      if (b == 0) return new long[]{1, 0};
      long[] p = extgcd(b, a % b);
      return new long[]{p[1], p[0] - a / b * p[1]};
    }

    long[] convolution(long[] a, long[] b) {
      a = ntt(a, 1);
      b = ntt(b, 1);
      for (int i = 0; i < a.length; i++) a[i] = a[i] * b[i] % mod;
      a = ntt(a, -1);
      return a;
    }
  }

  // Template
  public static void main(String[] args) {
    OutputStream outputStream = System.out;
    FastScanner in = new FastScanner();
    PrintWriter out = new PrintWriter(outputStream);
    Task solver = new Task();
    solver.solve(in, out);
    out.close();
  }
  private static class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int bufferLength = 0;

    private boolean hasNextByte() {
      if (ptr < bufferLength) {
        return true;
      } else {
        ptr = 0;
        try {
          bufferLength = in.read(buffer);
        } catch (IOException e) {
          e.printStackTrace();
        }
        if (bufferLength <= 0) {
          return false;
        }
      }
      return true;
    }

    private int readByte() {
      if (hasNextByte()) return buffer[ptr++];
      else return -1;
    }

    private static boolean isPrintableChar(int c) {
      return 33 <= c && c <= 126;
    }

    private void skipUnprintable() {
      while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
    }

    boolean hasNext() {
      skipUnprintable();
      return hasNextByte();
    }

    public String next() {
      if (!hasNext()) throw new NoSuchElementException();
      StringBuilder sb = new StringBuilder();
      int b = readByte();
      while (isPrintableChar(b)) {
        sb.appendCodePoint(b);
        b = readByte();
      }
      return sb.toString();
    }

    long nextLong() {
      if (!hasNext()) throw new NoSuchElementException();
      long n = 0;
      boolean minus = false;
      int b = readByte();
      if (b == '-') {
        minus = true;
        b = readByte();
      }
      if (b < '0' || '9' < b) {
        throw new NumberFormatException();
      }
      while (true) {
        if ('0' <= b && b <= '9') {
          n *= 10;
          n += b - '0';
        } else if (b == -1 || !isPrintableChar(b)) {
          return minus ? -n : n;
        } else {
          throw new NumberFormatException();
        }
        b = readByte();
      }
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    double[] nextDoubleArray(int n) {
      double[] array = new double[n];
      for (int i = 0; i < n; i++) {
        array[i] = nextDouble();
      }
      return array;
    }

    double[][] nextDoubleMap(int n, int m) {
      double[][] map = new double[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextDoubleArray(m);
      }
      return map;
    }

    public int nextInt() {
      return (int) nextLong();
    }

    public int[] nextIntArray(int n) {
      int[] array = new int[n];
      for (int i = 0; i < n; i++) {
        array[i] = nextInt();
      }
      return array;
    }
  }
}

Submission Info

Submission Time
Task C - 高速フーリエ変換
User kenkoooo
Language Java (OpenJDK 1.7.0)
Score 100
Code Size 6094 Byte
Status AC
Exec Time 1154 ms
Memory 40132 KB

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 917 ms 28272 KB
01_00_01 AC 829 ms 28440 KB
01_01_19 AC 830 ms 28416 KB
01_02_31 AC 839 ms 28428 KB
01_03_22 AC 845 ms 28408 KB
01_04_31 AC 830 ms 28352 KB
01_05_40 AC 841 ms 28392 KB
01_06_15 AC 841 ms 28384 KB
01_07_39 AC 853 ms 28396 KB
01_08_28 AC 844 ms 28388 KB
01_09_30 AC 841 ms 28392 KB
01_10_23 AC 841 ms 28424 KB
01_11_33 AC 838 ms 28340 KB
01_12_11 AC 837 ms 28364 KB
01_13_28 AC 847 ms 28336 KB
01_14_41 AC 834 ms 28420 KB
01_15_26 AC 827 ms 28388 KB
01_16_49 AC 827 ms 28416 KB
01_17_34 AC 828 ms 28456 KB
01_18_02 AC 822 ms 28416 KB
01_19_33 AC 826 ms 28368 KB
01_20_29 AC 832 ms 28396 KB
02_00_51254 AC 1071 ms 34400 KB
02_01_82431 AC 1149 ms 40132 KB
02_02_17056 AC 1047 ms 32552 KB
02_03_34866 AC 1073 ms 34124 KB
02_04_6779 AC 966 ms 30940 KB
02_05_65534 AC 1082 ms 35028 KB
02_06_65535 AC 1094 ms 35008 KB
02_07_65536 AC 1093 ms 34996 KB
02_08_65537 AC 1102 ms 34912 KB
02_09_65538 AC 1118 ms 35212 KB
02_10_100000 AC 1154 ms 39440 KB