Submission #3790241

---

Source Code Expand

use std::io::Write;

fn clp(mut x: usize) -> usize {
    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;
}

fn powmod(n: u64, d: u64, m: u64) -> u64 {
    let mut n = n;
    let mut d = d;
    let mut result: u64 = 1;
    while d > 0 {
        if d & 1 > 0 {
            result = (result * n) % m;
        }
        n = (n * n) % m;
        d >>= 1;
    }
    result
}

// gcd(x, m) == 1
fn invmod(x: u64, m: u64) -> u64 {
    powmod(x, m - 2, m)
}

const p: u64 = 3 * (1 << 30) + 1;
const alpha: u64 = 13;
const beta: u64 = 1_734_506_024; // beta == invmod(alpha, p)

fn fft(f: &mut Vec<u64>, n: usize, is_inverse: bool) {
    if n == 1 {
        return;
    }
    let mut f0 = vec![0; n / 2];
    let mut f1 = vec![0; n / 2];
    for i in 0..n / 2 {
        f0[i] = f[2 * i];
        f1[i] = f[2 * i + 1];
    }
    fft(&mut f0, n / 2, is_inverse);
    fft(&mut f1, n / 2, is_inverse);
    let zeta;
    if is_inverse {
        zeta = powmod(beta, (p - 1) / (n as u64), p);
    } else {
        zeta = powmod(alpha, (p - 1) / (n as u64), p);
    }
    let mut pow_zeta: u64 = 1;
    for i in 0..n {
        f[i] = (f0[i % (n / 2)] + (pow_zeta * f1[i % (n / 2)]) % p) % p;
        pow_zeta = (pow_zeta * zeta) % p;
    }
}

fn main() {
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());

    let N: usize = read_num();
    let n: usize = clp(2 * N + 1);
    let mut g: Vec<u64> = vec![0; n];
    let mut h: Vec<u64> = vec![0; n];
    for i in 1..N + 1 {
        let v = read_nums();
        g[i] = v[0];
        h[i] = v[1];
    }
    fft(&mut g, n, false); 
    fft(&mut h, n, false); 
    let mut f = vec![0; n];
    for i in 0..n {
        f[i] = (g[i] * h[i]) % p;
    }
    fft(&mut f, n, true);
    let inv_n: u64 = invmod(n as u64, p);
    for i in 1..2 * N + 1 {
        writeln!(out, "{}", (f[i] * inv_n) % p);
    }

    out.flush().unwrap();
}

fn read_str() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s
}

fn read_num<T>() -> T where 
    T: std::str::FromStr,
    T::Err: std::fmt::Debug {
    read_str().trim().parse().unwrap()
}

fn read_nums<T>() -> Vec<T> where
    T: std::str::FromStr,
    T::Err: std::fmt::Debug {
    let s = read_str();
    let a: Vec<&str> = s.split_whitespace().collect();
    let mut v: Vec<T> = Vec::new();
    for x in a {
        v.push(x.parse().unwrap());
    }
    v
}

Submission Info

Compile Error

warning: constant `p` should have an upper case name such as `P`, #[warn(non_upper_case_globals)] on by default
  --> ./Main.rs:32:1
   |
32 | const p: u64 = 3 * (1 << 30) + 1;
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

warning: constant `alpha` should have an upper case name such as `ALPHA`, #[warn(non_upper_case_globals)] on by default
  --> ./Main.rs:33:1
   |
33 | const alpha: u64 = 13;
   | ^^^^^^^^^^^^^^^^^^^^^^

warning: constant `beta` should have an upper case name such as `BETA`, #[warn(non_upper_case_globals)] on by default
  --> ./Main.rs:34:1
   |
34 | const beta: u64 = 1_734_506_024; // beta == invmod(alpha, p)
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

warning: variable `N` should have a snake case name such as `n`, #[warn(non_snake_case)] on by default
  --> ./Main.rs:65:9
   |
65 |     let N: usize = read_num();
   |         ^

warning: unused result which must be used, #[warn(unused_must_use)] on by default
  --> ./Main.rs:83:9
   |
83 |         writeln!(out, "{}", (f[i] * inv_n) % p);
   |   ...

Judge Result