結果
| 問題 |
No.1068 #いろいろな色 / Red and Blue and more various colors (Hard)
|
| コンテスト | |
| ユーザー |
 akakimidori
|
| 提出日時 | 2020-05-29 22:09:23 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 554 ms / 3,500 ms |
| コード長 | 17,389 bytes |
| コンパイル時間 | 13,323 ms |
| コンパイル使用メモリ | 402,952 KB |
| 実行使用メモリ | 20,804 KB |
| 最終ジャッジ日時 | 2024-11-06 05:03:10 |
| 合計ジャッジ時間 | 24,792 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 29 |
ソースコード
// ---------- begin ModInt ----------
mod modint {
pub const MOD: u32 = 998_244_353;
#[derive(Clone, Copy)]
pub struct ModInt(pub u32);
impl std::ops::Add for ModInt {
type Output = ModInt;
fn add(self, rhs: ModInt) -> ModInt {
let mut d = self.0 + rhs.0;
if d >= MOD {
d -= MOD;
}
ModInt(d)
}
}
impl std::ops::Sub for ModInt {
type Output = ModInt;
fn sub(self, rhs: ModInt) -> ModInt {
let d = if self.0 >= rhs.0 {
self.0 - rhs.0
} else {
self.0 + MOD - rhs.0
};
ModInt(d)
}
}
impl std::ops::Mul for ModInt {
type Output = ModInt;
fn mul(self, rhs: ModInt) -> ModInt {
ModInt((self.0 as u64 * rhs.0 as u64 % MOD as u64) as u32)
}
}
impl std::ops::Neg for ModInt {
type Output = ModInt;
fn neg(self) -> ModInt {
if self.0 == 0 {
self
} else {
ModInt(MOD - self.0)
}
}
}
impl std::ops::AddAssign for ModInt {
fn add_assign(&mut self, rhs: ModInt) {
*self = *self + rhs;
}
}
impl std::ops::SubAssign for ModInt {
fn sub_assign(&mut self, rhs: ModInt) {
*self = *self - rhs;
}
}
impl std::ops::MulAssign for ModInt {
fn mul_assign(&mut self, rhs: ModInt) {
*self = *self * rhs;
}
}
impl std::fmt::Display for ModInt {
fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {
write!(f, "{}", self.0)
}
}
impl std::str::FromStr for ModInt {
type Err = std::num::ParseIntError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let val = s.parse::<u32>()?;
Ok(ModInt::new(val))
}
}
impl From<usize> for ModInt {
fn from(v: usize) -> Self {
ModInt((v % MOD as usize) as u32)
}
}
#[allow(dead_code)]
impl ModInt {
pub fn new(v: u32) -> ModInt {
ModInt(v % MOD)
}
pub fn zero() -> ModInt {
ModInt(0)
}
pub fn one() -> ModInt {
ModInt(1)
}
pub fn zeta() -> ModInt {
ModInt(3)
}
pub fn pow(self, mut n: u32) -> ModInt {
let mut t = ModInt::one();
let mut s = self;
while n > 0 {
if n & 1 == 1 {
t = t * s;
}
s = s * s;
n >>= 1;
}
t
}
pub fn inv(self) -> ModInt {
assert!(self.0 > 0, "ModInt inv called with 0");
self.pow(MOD - 2)
}
}
}
// ---------- end ModInt ----------
// ---------- begin Precalc ----------
#[allow(dead_code)]
mod precalc {
use super::modint::*;
struct Precalc {
inv: Vec<ModInt>,
fact: Vec<ModInt>,
ifact: Vec<ModInt>,
}
impl Precalc {
pub fn new(n: usize) -> Precalc {
let mut inv = vec![ModInt::one(); n + 1];
let mut fact = vec![ModInt::one(); n + 1];
let mut ifact = vec![ModInt::one(); n + 1];
for i in 2..(n + 1) {
inv[i] = -inv[MOD as usize % i] * ModInt(MOD / i as u32);
fact[i] = fact[i - 1] * i.into();
ifact[i] = ifact[i - 1] * inv[i];
}
Precalc {
inv: inv,
fact: fact,
ifact: ifact,
}
}
pub fn fact(&self, n: usize) -> ModInt {
self.fact[n]
}
pub fn comb(&self, n: usize, k: usize) -> ModInt {
if n < k {
ModInt::zero()
} else {
self.fact[n] * self.ifact[k] * self.ifact[n - k]
}
}
pub fn inv(&self, n: usize) -> ModInt {
self.inv[n]
}
}
}
// ---------- end Precalc ----------
// ---------- begin NTT ----------
#[allow(dead_code)]
mod transform {
use super::modint::*;
pub fn ntt(f: &mut [ModInt]) {
let n = f.len();
assert!(n.count_ones() == 1);
let len = n.trailing_zeros() as usize;
let mut zeta = Vec::with_capacity(len);
let mut r = ModInt(3).pow((MOD - 1) >> len);
for _ in 0..len {
zeta.push(r);
r = r * r;
}
for (k, &z) in zeta.iter().rev().enumerate().rev() {
let m = 1 << k;
for f in f.chunks_exact_mut(2 * m) {
let mut q = ModInt::one();
let (x, y) = f.split_at_mut(m);
for (x, y) in x.iter_mut().zip(y.iter_mut()) {
let a = *x;
let b = *y;
*x = a + b;
*y = (a - b) * q;
q *= z;
}
}
}
}
pub fn intt(f: &mut [ModInt]) {
let n = f.len();
assert!(n.count_ones() == 1);
let len = n.trailing_zeros() as usize;
let mut zeta = Vec::with_capacity(len);
let mut r = ModInt(3).inv().pow((MOD - 1) >> len);
for _ in 0..len {
zeta.push(r);
r = r * r;
}
for (k, &z) in zeta.iter().rev().enumerate() {
let m = 1 << k;
for f in f.chunks_exact_mut(2 * m) {
let mut q = ModInt::one();
let (x, y) = f.split_at_mut(m);
for (x, y) in x.iter_mut().zip(y.iter_mut()) {
let a = *x;
let b = *y * q;
*x = a + b;
*y = a - b;
q *= z;
}
}
}
let ik = ModInt(f.len() as u32).inv();
for f in f.iter_mut() {
*f *= ik;
}
}
pub fn multiply(a: &[ModInt], b: &[ModInt]) -> Vec<ModInt> {
if a.is_empty() || b.is_empty() {
return vec![];
}
let n = a.len() + b.len() - 1;
let mut k = 1;
while k < n {
k *= 2;
}
assert!(k <= (1 << 23));
let mut f = Vec::with_capacity(k);
let mut g = Vec::with_capacity(k);
f.extend_from_slice(a);
f.resize(k, ModInt::zero());
ntt(&mut f);
g.extend_from_slice(b);
g.resize(k, ModInt::zero());
ntt(&mut g);
for (f, g) in f.iter_mut().zip(g.iter()) {
*f *= *g;
}
intt(&mut f);
f.truncate(n);
f
}
}
// ---------- end NTT ----------
// ---------- begin Polynomial ----------
#[allow(dead_code)]
mod poly {
use super::modint::*;
use super::transform;
use std;
#[derive(Clone)]
pub struct Polynomial {
pub a: Vec<ModInt>,
}
impl Polynomial {
pub fn new(a: Vec<ModInt>) -> Self {
let mut a = Polynomial { a: a };
a.fix();
a
}
pub fn from_slice(a: &[ModInt]) -> Self {
let mut b = Vec::with_capacity(a.len());
b.extend_from_slice(a);
Self::new(b)
}
pub fn zero() -> Self {
Polynomial::new(vec![])
}
pub fn one() -> Self {
Polynomial::new(vec![ModInt::one()])
}
pub fn get(&self, x: usize) -> ModInt {
self.a.get(x).cloned().unwrap_or(ModInt::zero())
}
pub fn len(&self) -> usize {
self.a.len()
}
pub fn reverse(&self, n: usize) -> Self {
assert!(self.len() >= n);
let mut a = Vec::with_capacity(n);
a.extend_from_slice(&self.a);
a.resize(n, ModInt::zero());
a.reverse();
Self::new(a)
}
pub fn truncate(&self, n: usize) -> Self {
let mut b = self.a.clone();
b.truncate(n);
Polynomial::new(b)
}
pub fn eval(&self, x: ModInt) -> ModInt {
let mut ans = ModInt::zero();
for a in self.a.iter().rev() {
ans = ans * x + *a;
}
ans
}
pub fn fix(&mut self) {
while let Some(&v) = self.a.last() {
if v.0 == 0 {
self.a.pop();
} else {
break;
}
}
}
pub fn derivative(&self) -> Self {
if self.len() < 2 {
return Polynomial::zero();
}
let mut b = vec![ModInt::zero(); self.len() - 1];
for (i, (b, a)) in b.iter_mut().zip(self.a.iter().skip(1)).enumerate() {
*b = *a * ModInt(i as u32 + 1);
}
Polynomial::new(b)
}
pub fn integral(&self) -> Self {
if self.len() < 1 {
return Polynomial::zero();
}
let mut b = vec![ModInt::zero(); self.len() + 1];
let mut inv = vec![ModInt::one(); self.len() + 1];
b[1] = self.a[0];
for (i, (b, a)) in b[1..].iter_mut().zip(self.a.iter()).enumerate().skip(1) {
let k = i + 1;
inv[k] = -inv[MOD as usize % k] * ModInt(MOD / k as u32);
*b = *a * inv[k];
}
Polynomial::new(b)
}
pub fn add(&self, rhs: &Self) -> Self {
let mut ans = vec![ModInt::zero(); std::cmp::max(self.a.len(), rhs.a.len())];
for (ans, a) in ans.iter_mut().zip(self.a.iter()) {
*ans = *a;
}
for (ans, a) in ans.iter_mut().zip(rhs.a.iter()) {
*ans += *a;
}
Polynomial::new(ans)
}
pub fn add_assign(&mut self, rhs: &Self) {
if self.len() < rhs.len() {
self.a.resize(rhs.len(), ModInt::zero());
}
for (a, b) in self.a.iter_mut().zip(rhs.a.iter()) {
*a += *b;
}
}
pub fn sub(&self, rhs: &Self) -> Self {
let mut ans = vec![ModInt::zero(); std::cmp::max(self.a.len(), rhs.a.len())];
for (ans, a) in ans.iter_mut().zip(self.a.iter()) {
*ans = *a;
}
for (ans, a) in ans.iter_mut().zip(rhs.a.iter()) {
*ans -= *a;
}
Polynomial::new(ans)
}
pub fn sub_assign(&mut self, rhs: &Self) {
if self.len() < rhs.len() {
self.a.resize(rhs.len(), ModInt::zero());
}
for (a, b) in self.a.iter_mut().zip(rhs.a.iter()) {
*a -= *b;
}
}
pub fn mul(&self, rhs: &Self) -> Self {
Self::new(transform::multiply(&self.a, &rhs.a))
}
pub fn inverse(&self, n: usize) -> Self {
assert!(self.a[0].0 > 0);
let len = n.next_power_of_two();
assert!(2 * len <= (1 << 23));
let mut b = Vec::with_capacity(len);
b.push(self.a[0].inv());
let mut f = Vec::with_capacity(2 * len);
let mut g = Vec::with_capacity(2 * len);
let mut size = 1;
while b.len() < n {
size <<= 1;
f.clear();
f.extend_from_slice(&b);
f.resize(2 * size, ModInt::zero());
g.clear();
if self.a.len() >= size {
g.extend_from_slice(&self.a[..size]);
} else {
g.extend_from_slice(&self.a);
}
g.resize(2 * size, ModInt::zero());
transform::ntt(&mut f);
transform::ntt(&mut g);
for (g, f) in g.iter_mut().zip(f.iter()) {
*g *= *f * *f;
}
transform::intt(&mut g);
b.resize(size, ModInt::zero());
for (b, g) in b.iter_mut().zip(g.iter()) {
*b = *b + *b - *g;
}
}
b.truncate(n);
Polynomial::new(b)
}
pub fn div_rem(&self, rhs: &Self) -> (Self, Self) {
let n = self.len();
let m = rhs.len();
assert!(m > 0);
if n < m {
return (Polynomial::zero(), self.clone());
}
let ia = self.reverse(n).truncate(n - m + 1);
let ib = rhs.reverse(m).inverse(n - m + 1);
let id = ia.mul(&ib).truncate(n - m + 1);
let div = id.reverse(n - m + 1);
let rem = self.sub(&rhs.mul(&div)).truncate(m - 1);
(div, rem)
}
pub fn rem(&self, rhs: &Self) -> Self {
self.div_rem(rhs).1
}
pub fn log(&self, n: usize) -> Self {
assert!(self.len() > 0 && self.a[0].0 == 1);
self.derivative()
.mul(&self.inverse(n))
.truncate(n - 1)
.integral()
}
pub fn exp(&self, n: usize) -> Self {
assert!(self.len() > 0 && self.a[0].0 == 0 && n <= (1 << 23));
let mut b = Polynomial::new(vec![ModInt::one()]);
let mut size = 1;
while size < n {
size <<= 1;
let f = b.log(size);
let f = Polynomial::from_slice(&self.a[..std::cmp::min(self.len(), size)]).sub(&f);
b = b.add(&b.mul(&f)).truncate(size);
}
b.truncate(n)
}
pub fn multi_eval(&self, x: &[ModInt]) -> Vec<ModInt> {
let size = x.len().next_power_of_two();
let mut seg = vec![Some(Polynomial::one()); 2 * size];
for (seg, x) in seg[size..].iter_mut().zip(x.iter()) {
*seg = Some(Polynomial::from_slice(&[-*x, ModInt::one()]));
}
for i in (1..size).rev() {
seg[i] = Some(
seg[2 * i]
.as_ref()
.unwrap()
.mul(seg[2 * i + 1].as_ref().unwrap()),
);
}
let mut rem = vec![None; 2 * size];
rem[1] = Some(self.rem(&seg[1].take().unwrap()));
for i in 1..size {
let a = rem[i].take().unwrap();
rem[2 * i] = Some(a.rem(&seg[2 * i].take().unwrap()));
rem[2 * i + 1] = Some(a.rem(&seg[2 * i + 1].take().unwrap()));
}
let mut ans = Vec::with_capacity(x.len());
for a in rem[size..].iter_mut().take(x.len()) {
ans.push(a.take().unwrap().get(0));
}
ans
}
pub fn interpolation(x: &[ModInt], y: &[ModInt]) -> Self {
assert!(x.len() > 0 && x.len() == y.len());
let size = x.len().next_power_of_two();
let mut p = vec![Polynomial::one(); 2 * size];
for (p, x) in p[size..].iter_mut().zip(x.iter()) {
*p = Polynomial::new(vec![-*x, ModInt::one()]);
}
for i in (1..size).rev() {
p[i] = p[2 * i].mul(&p[2 * i + 1]);
}
let z = p[1].derivative().multi_eval(x);
let mut a = vec![Polynomial::zero(); 2 * size];
for (a, (z, y)) in a[size..].iter_mut().zip(z.iter().zip(y.iter())) {
*a = Polynomial::new(vec![*y * z.inv()]);
}
for i in (1..size).rev() {
a[i] = a[2 * i]
.mul(&p[2 * i + 1])
.add(&a[2 * i + 1].mul(&p[2 * i]));
}
a.swap_remove(1)
}
}
}
// ---------- end Polynomial ----------
//https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 より
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
input_inner!{iter, $($r)*}
};
($($r:tt)*) => {
let s = {
use std::io::Read;
let mut s = String::new();
std::io::stdin().read_to_string(&mut s).unwrap();
s
};
let mut iter = s.split_whitespace();
input_inner!{iter, $($r)*}
};
}
macro_rules! input_inner {
($iter:expr) => {};
($iter:expr, ) => {};
($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($iter, $t);
input_inner!{$iter $($r)*}
};
}
macro_rules! read_value {
($iter:expr, ( $($t:tt),* )) => {
( $(read_value!($iter, $t)),* )
};
($iter:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
};
($iter:expr, chars) => {
read_value!($iter, String).chars().collect::<Vec<char>>()
};
($iter:expr, usize1) => {
read_value!($iter, usize) - 1
};
($iter:expr, $t:ty) => {
$iter.next().unwrap().parse::<$t>().expect("Parse error")
};
}
//
use poly::*;
use modint::*;
use std::io::Write;
fn calc(a: &[Polynomial]) -> Polynomial {
if a.len() == 1 {
a[0].clone()
} else {
let m = a.len() / 2;
let (a, b) = a.split_at(m);
calc(a).mul(&calc(b))
}
}
fn run() {
let out = std::io::stdout();
let mut out = std::io::BufWriter::new(out.lock());
input! {
n: usize,
q: usize,
a: [usize; n],
b: [usize; q],
}
let a = a.into_iter().map(|a| {
let a = ModInt::from(a - 1);
Polynomial::from_slice(&[a, ModInt::one()])
}).collect::<Vec<_>>();
let ans = calc(&a);
for b in b {
writeln!(out, "{}", ans.get(b)).ok();
}
}
fn main() {
run();
}