Advertisement
Guest User

Untitled

a guest
Feb 26th, 2020
146
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.55 KB | None | 0 0
  1. /*
  2. Author : quickn (quickn.ga)
  3. Email : quickwshell@gmail.com
  4. */
  5.  
  6. use std::io::{self, BufReader, BufWriter, Write, BufRead};
  7.  
  8. const P: u64 = 998244353;
  9. const G: u64 = 15311432;
  10. const SHIFT: u8 = 23;
  11. const N: usize = 8388608;
  12.  
  13. static mut POW_MOD_G: [u32;N] = [0;N];
  14.  
  15. fn pow_mod(a_t: u64, x: u64) -> u64 {
  16. let mut r: u64 = 1;
  17. let mut exp: u64 = x;
  18. let mut a: u64 = a_t;
  19. while exp != 0 {
  20. if exp & 1 == 1 {
  21. r = (r*a) % P;
  22. }
  23. a = (a*a) % P;
  24. exp >>= 1;
  25. }
  26. r
  27. }
  28.  
  29. fn fft(a: Vec<u64>, inv: bool) -> Vec<u64> {
  30. let n = a.len();
  31. let mut arr = a.clone();
  32. let (mut i, mut j): (usize, usize) = (1, 0);
  33. while i < n {
  34. let mut bit = n >> 1;
  35. while j >= bit {
  36. j -= bit;
  37. bit >>= 1;
  38. }
  39. j += bit;
  40. if i < j { arr.swap(i, j); }
  41. i += 1;
  42. }
  43. for l in 0..SHIFT {
  44. let m: usize = 1 << l;
  45. 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;
  46. for k in (0..n).step_by(m << 1) {
  47. let mut omega = 1;
  48. for j in 0..m {
  49. let t = (omega*arr[(k+j+m) as usize]) % P;
  50. let u = arr[(k+j) as usize];
  51. arr[(k+j) as usize] = (u + t) % P;
  52. arr[(k+j+m) as usize] = (((P as i64) + (u as i64) - (t as i64)) % P as i64) as u64 % P;
  53. omega = (omega*omega_m) % P;
  54. }
  55. }
  56. }
  57. match inv {
  58. true => {let n_inv = pow_mod(n as u64, P-2 as u64); arr.iter().map(|a| (a*n_inv) % P).collect()},
  59. _ => arr,
  60. }
  61. }
  62.  
  63. fn mut_polynomial(a: Vec<u64>) -> Vec<u64> {
  64. pre_processing();
  65. let mut p = a.clone();
  66. p.resize(N, 0);
  67. p = fft(p, false);
  68. for i in 0..N {
  69. p[i] = (p[i]*p[i]) % P;
  70. }
  71. fft(p, true)
  72. }
  73.  
  74. fn pre_processing() {
  75. let mut k: u64 = 1;
  76. unsafe { POW_MOD_G[0] = 1; }
  77. for i in 1..N {
  78. k = (k*G) % P;
  79. unsafe { POW_MOD_G[i as usize] = k as u32; }
  80. }
  81. }
  82.  
  83. fn main() {
  84. let mut sout = BufWriter::new(io::stdout());
  85. let mut sin = BufReader::new(io::stdin());
  86. let mut buf = String::new();
  87. sin.read_line(&mut buf).unwrap();
  88. let n: u32 = buf.trim().parse().unwrap();
  89. let mut arr: Vec<u64> = Vec::new();
  90. arr.resize(n as usize, 1);
  91. let res = mut_polynomial(arr.clone());
  92. for i in 0..(n << 1) {
  93. write!(sout, "{} ", res[i as usize]).unwrap();
  94. }
  95. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement