Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Author : quickn (quickn.ga)
- Email : quickwshell@gmail.com
- */
- use std::io::{self, BufReader, BufWriter, Write, BufRead};
- const P: u64 = 998244353;
- const G: u64 = 15311432;
- const SHIFT: u8 = 23;
- const N: usize = 8388608;
- static mut POW_MOD_G: [u32;N] = [0;N];
- fn pow_mod(a_t: u64, x: u64) -> u64 {
- let mut r: u64 = 1;
- let mut exp: u64 = x;
- let mut a: u64 = a_t;
- while exp != 0 {
- if exp & 1 == 1 {
- r = (r*a) % P;
- }
- a = (a*a) % P;
- exp >>= 1;
- }
- r
- }
- fn fft(a: Vec<u64>, inv: bool) -> Vec<u64> {
- let n = a.len();
- let mut arr = a.clone();
- let (mut i, mut j): (usize, usize) = (1, 0);
- while i < n {
- let mut bit = n >> 1;
- while j >= bit {
- j -= bit;
- bit >>= 1;
- }
- j += bit;
- if i < j { arr.swap(i, j); }
- i += 1;
- }
- for l in 0..SHIFT {
- let m: usize = 1 << l;
- let omega_m = if inv { unsafe { POW_MOD_G[(N as u64 - (1 << (SHIFT-l-1)) as u64) as usize] } } else { unsafe { POW_MOD_G[(1 << (SHIFT-l-1)) as usize] } } as u64;
- for k in (0..n).step_by(m << 1) {
- let mut omega = 1;
- for j in 0..m {
- let t = (omega*arr[(k+j+m) as usize]) % P;
- let u = arr[(k+j) as usize];
- arr[(k+j) as usize] = (u + t) % P;
- arr[(k+j+m) as usize] = (((P as i64) + (u as i64) - (t as i64)) % P as i64) as u64 % P;
- omega = (omega*omega_m) % P;
- }
- }
- }
- match inv {
- true => {let n_inv = pow_mod(n as u64, P-2 as u64); arr.iter().map(|a| (a*n_inv) % P).collect()},
- _ => arr,
- }
- }
- fn mut_polynomial(a: Vec<u64>) -> Vec<u64> {
- pre_processing();
- let mut p = a.clone();
- p.resize(N, 0);
- p = fft(p, false);
- for i in 0..N {
- p[i] = (p[i]*p[i]) % P;
- }
- fft(p, true)
- }
- fn pre_processing() {
- let mut k: u64 = 1;
- unsafe { POW_MOD_G[0] = 1; }
- for i in 1..N {
- k = (k*G) % P;
- unsafe { POW_MOD_G[i as usize] = k as u32; }
- }
- }
- fn main() {
- let mut sout = BufWriter::new(io::stdout());
- let mut sin = BufReader::new(io::stdin());
- let mut buf = String::new();
- sin.read_line(&mut buf).unwrap();
- let n: u32 = buf.trim().parse().unwrap();
- let mut arr: Vec<u64> = Vec::new();
- arr.resize(n as usize, 1);
- let res = mut_polynomial(arr.clone());
- for i in 0..(n << 1) {
- write!(sout, "{} ", res[i as usize]).unwrap();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement