#983986 (Rust) No.2763 Macaron Gift Box

提出ソース
結果

問題	No.2763 Macaron Gift Box
ユーザー	CoCo_Japan_pan
提出日時	2024-05-28 23:23:19
言語	Rust (1.77.0 + proconio)
結果	AC
実行時間	733 ms / 3,000 ms
コード長	25,698 bytes
コンパイル時間	14,892 ms
コンパイル使用メモリ	401,148 KB
実行使用メモリ	12,456 KB
最終ジャッジ日時	2024-05-28 23:23:39
合計ジャッジ時間	17,713 ms
ジャッジサーバーID （参考情報）	judge4 / judge3
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,812 KB
testcase_01	AC	0 ms 6,940 KB
testcase_02	AC	1 ms 6,940 KB
testcase_03	AC	1 ms 6,944 KB
testcase_04	AC	1 ms 6,944 KB
testcase_05	AC	1 ms 6,944 KB
testcase_06	AC	0 ms 6,944 KB
testcase_07	AC	283 ms 7,072 KB
testcase_08	AC	65 ms 6,944 KB
testcase_09	AC	140 ms 6,944 KB
testcase_10	AC	634 ms 12,296 KB
testcase_11	AC	630 ms 12,328 KB
testcase_12	AC	733 ms 12,452 KB
testcase_13	AC	681 ms 12,456 KB
testcase_14	AC	64 ms 6,944 KB
testcase_15	AC	65 ms 6,940 KB
testcase_16	AC	65 ms 6,944 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#![allow(unused_imports)]
#![allow(unused_macros)]
#![allow(non_snake_case)]
pub use __cargo_equip::prelude::*;

use fps_utils::Fps;
use proconio::marker::{Bytes, Chars, Isize1, Usize1};
use proconio::{fastout, input, input_interactive};
use static_modint::ModInt998244353 as MInt;

#[fastout]
fn main() {
    input! {
        N: usize,
        K: usize,
    }
    let log = {
        let mut ret = Fps::<MInt>::new(N + 1);
        // log(1-x^(K+1)i)
        for i in 1..=(N / (K + 1)) {
            let pow = i * (K + 1);
            for j in 1..=(N / pow) {
                ret.data[j * pow] -= MInt::new(j).inv();
            }
        }
        // -log(1-x^i)
        for i in 1..=N {
            for j in 1..=(N / i) {
                ret.data[j * i] += MInt::new(j).inv();
            }
        }
        ret
    };
    let ans = log.exp(N + 1);
    for i in 1..=N {
        if i == N {
            println!("{}", ans.data[i]);
        } else {
            print!("{} ", ans.data[i]);
        }
    }
}

#[macro_export]
macro_rules! mat {
    ($($e:expr),*) => { vec![$($e),*] };
    ($($e:expr,)*) => { vec![$($e),*] };
    ($e:expr; $d:expr) => { vec![$e; $d] };
    ($e:expr; $d:expr $(; $ds:expr)+) => { vec![mat![$e $(; $ds)*]; $d] };
}

#[macro_export]
macro_rules! chmin {
    ($a:expr, $b:expr) => {
        if $a > $b {
            $a = $b;
            true
        } else {
            false
        }
    };
}

#[macro_export]
macro_rules! chmax {
    ($a:expr, $b:expr) => {
        if $a < $b {
            $a = $b;
            true
        } else {
            false
        }
    };
}

/// https://maguro.dev/debug-macro/
#[macro_export]
macro_rules! debug {
    ($($a:expr),* $(,)*) => {
        #[cfg(debug_assertions)]
        eprintln!(concat!($("| ", stringify!($a), "={:?} "),*, "|"), $(&$a),*);
    };
}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `dynamic_modint 0.1.0 (git+ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git#b2298d0b9b42d4d31ab88d070e5f0001ddeadd8a)`       licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__dynamic_modint_0_1_0`
///  - `fps_utils 0.1.0 (git+ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git#b2298d0b9b42d4d31ab88d070e5f0001ddeadd8a)`            licensed under `CC0-1.0` as `crate::__cargo_equip::crates::fps_utils`
///  - `internal_bits 0.1.0 (git+ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git#b2298d0b9b42d4d31ab88d070e5f0001ddeadd8a)`        licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__internal_bits_0_1_0`
///  - `internal_type_traits 0.1.0 (git+ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git#b2298d0b9b42d4d31ab88d070e5f0001ddeadd8a)` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__internal_type_traits_0_1_0`
///  - `modint_traits 0.1.0 (git+ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git#b2298d0b9b42d4d31ab88d070e5f0001ddeadd8a)`        licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__modint_traits_0_1_0`
///  - `ntt 0.1.0 (git+ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git#b2298d0b9b42d4d31ab88d070e5f0001ddeadd8a)`                  licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__ntt_0_1_0`
///  - `static_modint 0.1.0 (git+ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git#b2298d0b9b42d4d31ab88d070e5f0001ddeadd8a)`        licensed under `CC0-1.0` as `crate::__cargo_equip::crates::static_modint`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod __dynamic_modint_0_1_0 {use crate::__cargo_equip::preludes::__dynamic_modint_0_1_0::*;pub use crate::__cargo_equip::macros::__dynamic_modint_0_1_0::*;use internal_type_traits::{One,Zero};use modint_traits::{ModInt,RemEuclidU32};use std::fmt::Debug;use std::fmt::Display;use std::iter::{Product,Sum};use std::marker::PhantomData;use std::num::ParseIntError;use std::ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Neg,Sub,SubAssign};use std::str::FromStr;use std::sync::OnceLock;pub trait ModContainer:'static+Debug+Clone+Copy+PartialEq+Eq+Default{fn get_static_modulus()->&'static OnceLock<u32>;fn modulus()->u32{*Self::get_static_modulus().get().expect("haven't set modulus")}fn set_modulus(modulus:u32){Self::get_static_modulus().set(modulus).expect("already set modulus")}}#[macro_export]macro_rules!__cargo_equip_macro_def___dynamic_modint_0_1_0_define_modint{($name:ident)=>{#[derive(Debug,Clone,Copy,PartialEq,Eq,Hash,Default)]pub struct$name{}impl$crate::__cargo_equip::crates::__dynamic_modint_0_1_0::ModContainer for$name{fn get_static_modulus()->&'static std::sync::OnceLock<u32>{static ONCE:std::sync::OnceLock<u32> =std::sync::OnceLock::new();&ONCE}}};}macro_rules!define_modint{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___dynamic_modint_0_1_0_define_modint!{$($tt)*})}#[derive(Debug,Clone,Copy,PartialEq,Eq,Hash,Default)]pub struct DynamicModInt<MOD:ModContainer>{value:u32,phantom:PhantomData<MOD>,}impl<MOD:ModContainer>Zero for DynamicModInt<MOD>{fn zero()->Self{Self::raw(0)}}impl<MOD:ModContainer>One for DynamicModInt<MOD>{fn one()->Self{Self::new(1)}}impl<MOD:ModContainer>Display for DynamicModInt<MOD>{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{write!(f,"{}",self.value)}}impl<MOD:ModContainer,T>Sum<T>for DynamicModInt<MOD>where Self:Add<T,Output=Self>,{fn sum<I:Iterator<Item=T>>(iter:I)->Self{iter.fold(Self::raw(0),Add::add)}}impl<MOD:ModContainer,T>Product<T>for DynamicModInt<MOD>where Self:Mul<T,Output=Self>,{fn product<I:Iterator<Item=T>>(iter:I)->Self{iter.fold(Self::new(1),Mul::mul)}}impl<MOD:ModContainer>FromStr for DynamicModInt<MOD>{type Err=ParseIntError;fn from_str(s:&str)->Result<Self,ParseIntError>{i64::from_str(s).map(Self::new)}}impl<MOD:ModContainer>DynamicModInt<MOD>{pub fn set_modulus(modulus:u32){MOD::set_modulus(modulus);}pub fn new<T:RemEuclidU32>(x:T)->Self{ModInt::new(x)}pub fn raw(x:u32)->Self{Self{value:x,phantom:PhantomData,}}pub fn value(&self)->u32{self.value}pub fn modulus()->u32{MOD::modulus()}pub fn pow(&self,n:u64)->Self{ModInt::pow(self,n)}pub fn inv(&self)->Self{ModInt::inv(self)}}impl<MOD:ModContainer>ModInt for DynamicModInt<MOD>{fn new<T:RemEuclidU32>(x:T)->Self{Self{value:x.rem_euclid_u32(MOD::modulus()),phantom:PhantomData,}}fn raw(x:u32)->Self{Self{value:x,phantom:PhantomData,}}fn value(&self)->u32{self.value}fn modulus()->u32{MOD::modulus()}}impl<MOD:ModContainer>Neg for DynamicModInt<MOD>{type Output=Self;fn neg(self)->Self{if self.value==0{Self{value:0,phantom:PhantomData,}}else{Self{value:DynamicModInt::<MOD>::modulus()-self.value,phantom:PhantomData,}}}}impl<MOD:ModContainer,T>Add<T>for DynamicModInt<MOD>where Self:AddAssign<T>,{type Output=Self;fn add(self,rhs:T)->Self{let mut res=self;res+=rhs;res}}impl<MOD:ModContainer>AddAssign for DynamicModInt<MOD>{fn add_assign(&mut self,rhs:Self){self.value+=rhs.value;if self.value>=DynamicModInt::<MOD>::modulus(){self.value-=DynamicModInt::<MOD>::modulus();}}}impl<MOD:ModContainer,T:RemEuclidU32>AddAssign<T>for DynamicModInt<MOD>{fn add_assign(&mut self,rhs:T){*self+=DynamicModInt::<MOD>::new(rhs);}}impl<MOD:ModContainer,T>Sub<T>for DynamicModInt<MOD>where Self:SubAssign<T>,{type Output=Self;fn sub(mut self,rhs:T)->Self{self-=rhs;self}}impl<MOD:ModContainer>SubAssign for DynamicModInt<MOD>{fn sub_assign(&mut self,rhs:Self){if self.value<rhs.value{self.value+=DynamicModInt::<MOD>::modulus();}self.value-=rhs.value;}}impl<MOD:ModContainer,T:RemEuclidU32>SubAssign<T>for DynamicModInt<MOD>{fn sub_assign(&mut self,rhs:T){*self-=DynamicModInt::<MOD>::new(rhs);}}impl<MOD:ModContainer,T>Mul<T>for DynamicModInt<MOD>where Self:MulAssign<T>,{type Output=Self;fn mul(mut self,rhs:T)->Self{self*=rhs;self}}impl<MOD:ModContainer>MulAssign for DynamicModInt<MOD>{fn mul_assign(&mut self,rhs:Self){self.value=(self.value as u64*rhs.value as u64%DynamicModInt::<MOD>::modulus()as u64)as u32;}}impl<MOD:ModContainer,T:RemEuclidU32>MulAssign<T>for DynamicModInt<MOD>{fn mul_assign(&mut self,rhs:T){*self*=DynamicModInt::<MOD>::new(rhs);}}impl<MOD:ModContainer,T>Div<T>for DynamicModInt<MOD>where Self:DivAssign<T>,{type Output=Self;fn div(self,rhs:T)->Self{let mut res=self;res/=rhs;res}}#[allow(clippy::suspicious_op_assign_impl)]impl<MOD:ModContainer>DivAssign for DynamicModInt<MOD>{fn div_assign(&mut self,rhs:Self){*self*=rhs.inv();}}impl<MOD:ModContainer,T:RemEuclidU32>DivAssign<T>for DynamicModInt<MOD>{fn div_assign(&mut self,rhs:T){*self/=DynamicModInt::<MOD>::new(rhs);}}macro_rules!impl_from_primitive{($($t:ty),*)=>{$(impl<MOD:ModContainer>From<$t>for DynamicModInt<MOD>{fn from(x:$t)->Self{DynamicModInt::new(x)}})*}}impl_from_primitive!(i8,i16,i32,i64,isize,i128,u8,u16,u32,u64,usize,u128);}
        pub mod fps_utils {use crate::__cargo_equip::preludes::fps_utils::*;use internal_bits::ceil_log2;use ntt::{convolution,ConvHelper};use std::fmt::Display;use std::ops::{Add,AddAssign,Mul,MulAssign,Neg,Sub,SubAssign};#[derive(Debug,Clone,PartialEq,Eq)]pub struct Fps<T:ConvHelper>{pub data:Vec<T>,}impl<T:ConvHelper>Display for Fps<T>{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{if self.is_empty(){return Ok(());}write!(f,"{}",self.data[0])?;for x in self.data.iter().skip(1){write!(f," {}",x)?;}Ok(())}}impl<T:ConvHelper,S>From<Vec<S>>for Fps<T>where T:From<S>,{fn from(data:Vec<S>)->Self{Self{data:data.into_iter().map(T::from).collect(),}}}impl<T:ConvHelper>Fps<T>{pub fn new(deg:usize)->Self{Self{data:vec![T::raw(0);deg],}}pub fn len(&self)->usize{self.data.len()}pub fn is_empty(&self)->bool{self.data.is_empty()}pub fn truncate(&self,n:usize)->Self{let size=self.len().min(n);Self{data:self.data[..size].to_vec(),}}}#[allow(clippy::needless_range_loop)]impl<T:ConvHelper>Fps<T>{pub fn differential(&self)->Self{let n=self.len();let mut data=vec![T::raw(0);n-1];for i in 0..n-1{data[i]=self.data[i+1]*T::new(i+1);}Fps::from(data)}pub fn integral(&self)->Self{let n=self.len();let mut data=vec![T::raw(0);n+1];for i in 1..n+1{data[i]=self.data[i-1]/T::new(i);}Fps::from(data)}pub fn inverse(&self,deg:usize)->Self{assert_ne!(self.data[0].value(),0);let mut g=Fps::from(vec![self.data[0].inv()]);let log=ceil_log2(deg as u32)as usize;for i in 1..=log{g=(&g*T::new(2)-&(&g*&g*self.truncate(1<<i))).truncate(1<<i);}g.truncate(deg)}pub fn log(&self,deg:usize)->Self{assert_eq!(self.data[0].value(),1);let f=self.differential()*self.inverse(deg);f.truncate(deg-1).integral()}pub fn exp(&self,deg:usize)->Self{assert_eq!(self.data[0].value(),0);let mut g=Fps::from(vec![T::new(1_u8)]);let log=ceil_log2(deg as u32)as usize;for i in 1..=log{let mut f=self.truncate(1<<i);f.data[0]+=T::new(1_u8);g=(&g*&(f-&g.log(1<<i))).truncate(1<<i);}g.truncate(deg)}}impl<T:ConvHelper>Add<&Self>for Fps<T>{type Output=Fps<T>;fn add(mut self,rhs:&Self)->Self::Output{self+=rhs;self}}impl<T:ConvHelper>Add for&Fps<T>{type Output=Fps<T>;fn add(self,rhs:Self)->Self::Output{let(big,small)=if self.len()<rhs.len(){(rhs,self)}else{(self,rhs)};let mut data=big.data.clone();for(idx,&s)in small.data.iter().enumerate(){data[idx]+=s;}Fps::from(data)}}impl<T:ConvHelper>AddAssign<&Self>for Fps<T>{fn add_assign(&mut self,rhs:&Self){let n=self.len().max(rhs.len());self.data.resize(n,T::raw(0));for(idx,&r)in rhs.data.iter().enumerate(){self.data[idx]+=r;}}}impl<T:ConvHelper>Sub<&Self>for Fps<T>{type Output=Fps<T>;fn sub(mut self,rhs:&Self)->Self::Output{self-=rhs;self}}impl<T:ConvHelper>Sub for&Fps<T>{type Output=Fps<T>;fn sub(self,rhs:Self)->Self::Output{let(big,small)=if self.len()<rhs.len(){(rhs,self)}else{(self,rhs)};let mut data=big.data.clone();for(idx,&s)in small.data.iter().enumerate(){data[idx]-=s;}Fps::from(data)}}impl<T:ConvHelper>SubAssign<&Self>for Fps<T>{fn sub_assign(&mut self,rhs:&Self){let n=self.len().max(rhs.len());self.data.resize(n,T::raw(0));for(idx,&r)in rhs.data.iter().enumerate(){self.data[idx]-=r;}}}impl<T:ConvHelper>Mul for&Fps<T>{type Output=Fps<T>;fn mul(self,rhs:Self)->Self::Output{Fps::from(convolution(&self.data,&rhs.data))}}impl<T:ConvHelper>Mul for Fps<T>{type Output=Fps<T>;fn mul(self,rhs:Self)->Self::Output{&self*&rhs}}impl<T:ConvHelper>Mul<&Self>for Fps<T>{type Output=Fps<T>;fn mul(mut self,rhs:&Self)->Self::Output{self*=rhs;self}}impl<T:ConvHelper>MulAssign<&Self>for Fps<T>{fn mul_assign(&mut self,rhs:&Self){self.data=convolution(&self.data,&rhs.data);}}impl<T:ConvHelper>Mul<T>for Fps<T>{type Output=Fps<T>;fn mul(mut self,rhs:T)->Self::Output{self*=rhs;self}}impl<T:ConvHelper>Mul<T>for&Fps<T>{type Output=Fps<T>;fn mul(self,rhs:T)->Self::Output{let ret=self.clone();ret*rhs}}impl<T:ConvHelper>MulAssign<T>for Fps<T>{fn mul_assign(&mut self,rhs:T){for x in self.data.iter_mut(){*x*=rhs;}}}impl<T:ConvHelper>Neg for Fps<T>{type Output=Fps<T>;fn neg(self)->Self::Output{Fps::from(self.data.into_iter().map(|x|-x).collect::<Vec<T>>())}}}
        pub mod __internal_bits_0_1_0 {pub fn ceil_log2(n:u32)->u32{32-n.saturating_sub(1).leading_zeros()}}
        pub mod __internal_type_traits_0_1_0 {use std::ops::{Add,AddAssign,Sub,SubAssign};pub trait Integral:Copy+Add<Output=Self>+AddAssign+Sub<Output=Self>+SubAssign+Ord+Zero+One+BoundedBelow+BoundedAbove{}pub trait Zero{fn zero()->Self;}pub trait One{fn one()->Self;}pub trait BoundedBelow{fn min_value()->Self;}pub trait BoundedAbove{fn max_value()->Self;}macro_rules!impl_integral{($($ty:ty),*)=>{$(impl Zero for$ty{#[inline]fn zero()->Self{0}}impl One for$ty{#[inline]fn one()->Self{1}}impl BoundedBelow for$ty{#[inline]fn min_value()->Self{Self::MIN}}impl BoundedAbove for$ty{#[inline]fn max_value()->Self{Self::MAX}}impl Integral for$ty{})*};}impl_integral!(i8,i16,i32,i64,i128,isize,u8,u16,u32,u64,u128,usize);}
        pub mod __modint_traits_0_1_0 {use std::fmt::{Debug,Display};use std::ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Neg,Sub,SubAssign};use std::str::FromStr;pub trait ModInt:Debug+Default+Clone+PartialEq+Eq+Display+Copy+Add<Output=Self>+Sub<Output=Self>+Mul<Output=Self>+Div<Output=Self>+AddAssign+SubAssign+MulAssign+DivAssign+Neg<Output=Self>+FromStr{fn new<T:RemEuclidU32>(x:T)->Self;fn raw(x:u32)->Self;fn value(&self)->u32;fn modulus()->u32;fn pow(&self,mut n:u64)->Self{let mut ret=Self::new(1);let mut base=*self;while n>0{if n&1==1{ret*=base;}base*=base;n>>=1;}ret}#[inline]fn inv(&self)->Self{let(g,x)=inv_gcd(self.value(),Self::modulus());assert_eq!(g,1);Self::raw(x)}}fn inv_gcd(a:u32,b:u32)->(u32,u32){assert!(a<b);if a==0{return(b,0);}let mut s=b;let mut t=a;let mut m0=0_i32;let mut m1=1_i32;while t!=0{let u=s/t;s-=t*u;m0-=m1*(u as i32);std::mem::swap(&mut s,&mut t);std::mem::swap(&mut m0,&mut m1);}if m0<0{m0+=(b/s)as i32;}(s,m0 as u32)}pub trait RemEuclidU32:Copy{fn rem_euclid_u32(self,modulus:u32)->u32;}impl RemEuclidU32 for u8{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{self as u32%modulus}}impl RemEuclidU32 for u16{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{self as u32%modulus}}impl RemEuclidU32 for u32{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{self%modulus}}impl RemEuclidU32 for u64{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{(self%modulus as u64)as u32}}impl RemEuclidU32 for usize{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{let casted:u64=self.try_into().unwrap();casted.rem_euclid_u32(modulus)}}impl RemEuclidU32 for u128{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{(self%modulus as u128)as u32}}#[inline]fn neg(val:u32,modulus:u32)->u32{if val==0{0}else{modulus-val}}macro_rules!impl_rem_euclid_u32_for_signed{($($t:ty),*)=>{$(impl RemEuclidU32 for$t{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{if self<0{neg(self.unsigned_abs().rem_euclid_u32(modulus),modulus)}else{self.unsigned_abs().rem_euclid_u32(modulus)}}})*};}impl_rem_euclid_u32_for_signed!(i8,i16,i32,i64,isize,i128);}
        pub mod __ntt_0_1_0 {use crate::__cargo_equip::preludes::__ntt_0_1_0::*;use dynamic_modint::{DynamicModInt,ModContainer};use modint_traits::ModInt;use static_modint::StaticModInt;const MOD_998244353:u32=998244353;const G_MOD1:u32=167772161;const G_MOD2:u32=469762049;const G_MOD3:u32=1224736769;fn prepare<const NTT_MOD:u32,const PRIMITIVE_ROOT:u32>()->([StaticModInt<NTT_MOD>;30],[StaticModInt<NTT_MOD>;30]){let g=StaticModInt::<NTT_MOD>::raw(PRIMITIVE_ROOT);let mut es=[StaticModInt::<NTT_MOD>::raw(0);30];let mut ies=[StaticModInt::<NTT_MOD>::raw(0);30];let cnt2=(NTT_MOD-1).trailing_zeros()as usize;let mut e=g.pow(((NTT_MOD-1)>>cnt2).into());let mut ie=e.inv();for i in(2..=cnt2).rev(){es[i-2]=e;ies[i-2]=ie;e*=e;ie*=ie;}for i in 1..30{es[i]*=es[i-1];ies[i]*=ies[i-1];}(es,ies)}fn ntt<const NTT_MOD:u32,const PRIMITIVE_ROOT:u32>(data:&mut[StaticModInt<NTT_MOD>],sum_e:&[StaticModInt<NTT_MOD>;30],){let size=data.len();assert!(size.is_power_of_two());let height=size.next_power_of_two().trailing_zeros();for ph in 1..=height{let w=1<<(ph-1);let p=1<<(height-ph);let mut now=StaticModInt::<NTT_MOD>::raw(1);for s in 0..w{let offset=s<<(height-ph+1);for i in 0..p{let l=data[i+offset];let r=data[i+offset+p]*now;data[i+offset]=l+r;data[i+offset+p]=l-r;}now*=sum_e[(!s).trailing_zeros()as usize];}}}fn intt<const NTT_MOD:u32,const PRIMITIVE_ROOT:u32>(data:&mut[StaticModInt<NTT_MOD>],sum_ie:&[StaticModInt<NTT_MOD>;30],){let size=data.len();assert!(size.is_power_of_two());let height=size.next_power_of_two().trailing_zeros();for ph in(1..=height).rev(){let w=1<<(ph-1);let p=1<<(height-ph);let mut inow=StaticModInt::<NTT_MOD>::raw(1);for s in 0..w{let offset=s<<(height-ph+1);for i in 0..p{let l=data[i+offset];let r=data[i+offset+p];data[i+offset]=l+r;data[i+offset+p]=(l-r)*inow;}inow*=sum_ie[(!s).trailing_zeros()as usize];}}}fn convolution_naive<M:ModInt>(a:&[M],b:&[M])->Vec<M>{let(n,m)=(a.len(),b.len());let mut ret=vec![M::raw(0);n+m-1];for(i,j)in(0..n).flat_map(|i|(0..m).map(move|j|(i,j))){ret[i+j]+=a[i]*b[j];}ret}fn convolution_ntt_friendly<const NTT_MOD:u32,const PRIMITIVE_ROOT:u32>(a:&[StaticModInt<NTT_MOD>],b:&[StaticModInt<NTT_MOD>],)->Vec<StaticModInt<NTT_MOD>>{if a.is_empty()||b.is_empty(){return vec![];}if a.len().min(b.len())<=60{return convolution_naive(a,b);}let n=a.len()+b.len()-1;let size=n.next_power_of_two();assert!((NTT_MOD-1)%size as u32==0);let mut a=a.to_owned();a.resize(size,StaticModInt::<NTT_MOD>::raw(0));let(sum_e,sum_ie)=prepare::<NTT_MOD,PRIMITIVE_ROOT>();ntt::<NTT_MOD,PRIMITIVE_ROOT>(&mut a,&sum_e);let mut b=b.to_owned();b.resize(size,StaticModInt::<NTT_MOD>::raw(0));ntt::<NTT_MOD,PRIMITIVE_ROOT>(&mut b,&sum_e);for(a,b)in a.iter_mut().zip(b){*a*=b;}intt::<NTT_MOD,PRIMITIVE_ROOT>(&mut a,&sum_ie);a.resize(n,StaticModInt::<NTT_MOD>::raw(0));let inv_size=StaticModInt::<NTT_MOD>::raw(size as u32).inv();for a in a.iter_mut(){*a*=inv_size;}a}fn convolution_aribtrary_u32_mod<M:ModInt>(a:&[M],b:&[M])->Vec<M>{let x=convolution_ntt_friendly::<G_MOD1,3>(a.iter().map(|x|StaticModInt::<G_MOD1>::new(x.value())).collect::<Vec<_>>().as_slice(),b.iter().map(|x|StaticModInt::<G_MOD1>::new(x.value())).collect::<Vec<_>>().as_slice(),);let y=convolution_ntt_friendly::<G_MOD2,3>(a.iter().map(|x|StaticModInt::<G_MOD2>::new(x.value())).collect::<Vec<_>>().as_slice(),b.iter().map(|x|StaticModInt::<G_MOD2>::new(x.value())).collect::<Vec<_>>().as_slice(),);let z=convolution_ntt_friendly::<G_MOD3,3>(a.iter().map(|x|StaticModInt::<G_MOD3>::new(x.value())).collect::<Vec<_>>().as_slice(),b.iter().map(|x|StaticModInt::<G_MOD3>::new(x.value())).collect::<Vec<_>>().as_slice(),);let m1_inv_m2=StaticModInt::<G_MOD2>::new(G_MOD1).inv();let m12_inv_m3=StaticModInt::<G_MOD3>::new(G_MOD1 as u64*G_MOD2 as u64).inv();let m12_mod=M::new(G_MOD1 as u64*G_MOD2 as u64);let mut ret=vec![M::raw(0);x.len()];for(i,r)in ret.iter_mut().enumerate(){let v1=((StaticModInt::<G_MOD2>::new(y[i].value())-StaticModInt::<G_MOD2>::new(x[i].value()))*m1_inv_m2).value();let v2=((StaticModInt::<G_MOD3>::new(z[i].value())-StaticModInt::<G_MOD3>::new(x[i].value())-StaticModInt::<G_MOD3>::new(G_MOD1)*StaticModInt::<G_MOD3>::new(v1))*m12_inv_m3).value();let constants=M::new(x[i].value())+M::new(G_MOD1)*M::new(v1)+m12_mod*M::new(v2);*r=constants;}ret}pub trait ConvHelper:ModInt{fn convolution(a:&[Self],b:&[Self])->Vec<Self>;}impl<const MOD:u32>ConvHelper for StaticModInt<MOD>{fn convolution(a:&[Self],b:&[Self])->Vec<Self>{match MOD{MOD_998244353|G_MOD1|G_MOD2|G_MOD3=>convolution_ntt_friendly::<MOD,3>(a,b),_=>convolution_aribtrary_u32_mod(a,b),}}}impl<MOD:ModContainer>ConvHelper for DynamicModInt<MOD>{fn convolution(a:&[Self],b:&[Self])->Vec<Self>{convolution_aribtrary_u32_mod(a,b)}}pub fn convolution<M:ConvHelper>(a:&[M],b:&[M])->Vec<M>{M::convolution(a,b)}}
        pub mod static_modint {use crate::__cargo_equip::preludes::static_modint::*;use internal_type_traits::{One,Zero};use modint_traits::{ModInt,RemEuclidU32};use std::fmt::Display;use std::iter::{Product,Sum};use std::ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Neg,Sub,SubAssign};use std::str::FromStr;pub type ModInt998244353=StaticModInt<998244353>;pub type ModInt1000000007=StaticModInt<1000000007>;#[derive(Debug,Clone,Copy,PartialEq,Eq,Hash,Default)]pub struct StaticModInt<const MOD:u32>{value:u32,}impl<const MOD:u32>Zero for StaticModInt<MOD>{fn zero()->Self{Self::raw(0)}}impl<const MOD:u32>One for StaticModInt<MOD>{fn one()->Self{Self::new(1)}}impl<const MOD:u32>Display for StaticModInt<MOD>{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{write!(f,"{}",self.value)}}impl<const MOD:u32,T>Sum<T>for StaticModInt<MOD>where Self:Add<T,Output=Self>,{fn sum<I:Iterator<Item=T>>(iter:I)->Self{iter.fold(Self::raw(0),Add::add)}}impl<const MOD:u32,T>Product<T>for StaticModInt<MOD>where Self:Mul<T,Output=Self>,{fn product<I:Iterator<Item=T>>(iter:I)->Self{iter.fold(Self::new(1),Mul::mul)}}impl<const MOD:u32>FromStr for StaticModInt<MOD>{type Err=<i64 as FromStr>::Err;fn from_str(s:&str)->Result<Self,Self::Err>{i64::from_str(s).map(Self::new)}}impl<const MOD:u32>StaticModInt<MOD>{#[inline]pub fn value(&self)->u32{self.value}#[inline]pub fn modulus()->u32{MOD}#[inline]pub fn new<T:RemEuclidU32>(x:T)->Self{ModInt::new(x)}#[inline]pub fn raw(x:u32)->Self{Self{value:x}}#[inline]pub fn pow(&self,n:u64)->Self{ModInt::pow(self,n)}#[inline]pub fn inv(&self)->Self{ModInt::inv(self)}}impl<const MOD:u32>ModInt for StaticModInt<MOD>{#[inline]fn value(&self)->u32{self.value}#[inline]fn modulus()->u32{MOD}#[inline]fn raw(x:u32)->Self{Self{value:x}}#[inline]fn new<T:RemEuclidU32>(x:T)->Self{Self{value:x.rem_euclid_u32(MOD),}}}impl<const MOD:u32>Neg for StaticModInt<MOD>{type Output=Self;#[inline]fn neg(self)->Self{if self.value==0{Self{value:0}}else{Self{value:MOD-self.value,}}}}impl<const MOD:u32,T>Add<T>for StaticModInt<MOD>where Self:AddAssign<T>,{type Output=Self;fn add(mut self,rhs:T)->Self{self+=rhs;self}}impl<const MOD:u32>AddAssign for StaticModInt<MOD>{fn add_assign(&mut self,rhs:Self){self.value+=rhs.value;if self.value>=MOD{self.value-=MOD;}}}impl<const MOD:u32,T:RemEuclidU32>AddAssign<T>for StaticModInt<MOD>{fn add_assign(&mut self,rhs:T){*self+=Self::new(rhs);}}impl<const MOD:u32,T>Sub<T>for StaticModInt<MOD>where Self:SubAssign<T>,{type Output=Self;fn sub(mut self,rhs:T)->Self{self-=rhs;self}}impl<const MOD:u32>SubAssign for StaticModInt<MOD>{fn sub_assign(&mut self,rhs:Self){if self.value<rhs.value{self.value+=MOD;}self.value-=rhs.value;}}impl<const MOD:u32,T:RemEuclidU32>SubAssign<T>for StaticModInt<MOD>{fn sub_assign(&mut self,rhs:T){*self-=Self::new(rhs);}}impl<const MOD:u32,T>Mul<T>for StaticModInt<MOD>where Self:MulAssign<T>,{type Output=Self;fn mul(mut self,rhs:T)->Self{self*=rhs;self}}impl<const MOD:u32>MulAssign for StaticModInt<MOD>{fn mul_assign(&mut self,rhs:Self){self.value=(self.value as u64*rhs.value as u64).rem_euclid_u32(MOD);}}impl<const MOD:u32,T:RemEuclidU32>MulAssign<T>for StaticModInt<MOD>{fn mul_assign(&mut self,rhs:T){*self*=Self::new(rhs);}}impl<const MOD:u32,T>Div<T>for StaticModInt<MOD>where Self:DivAssign<T>,{type Output=Self;fn div(mut self,rhs:T)->Self{self/=rhs;self}}#[allow(clippy::suspicious_op_assign_impl)]impl<const MOD:u32>DivAssign for StaticModInt<MOD>{fn div_assign(&mut self,rhs:Self){*self*=rhs.inv();}}impl<const MOD:u32,T:RemEuclidU32>DivAssign<T>for StaticModInt<MOD>{fn div_assign(&mut self,rhs:T){*self/=Self::new(rhs);}}macro_rules!impl_from_primitive{($($t:ty),*)=>{$(impl<const MOD:u32>From<$t>for StaticModInt<MOD>{fn from(x:$t)->Self{Self::new(x)}})*};}impl_from_primitive!(u8,u16,u32,u64,usize,u128,i8,i16,i32,i64,isize,i128);}
    }

    pub(crate) mod macros {
        pub mod __dynamic_modint_0_1_0 {pub use crate::__cargo_equip_macro_def___dynamic_modint_0_1_0_define_modint as define_modint;}
        pub mod fps_utils {}
        pub mod __internal_bits_0_1_0 {}
        pub mod __internal_type_traits_0_1_0 {}
        pub mod __modint_traits_0_1_0 {}
        pub mod __ntt_0_1_0 {}
        pub mod static_modint {}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}

    mod preludes {
        pub mod __dynamic_modint_0_1_0 {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__internal_type_traits_0_1_0 as internal_type_traits,__modint_traits_0_1_0 as modint_traits};}
        pub mod fps_utils {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__internal_bits_0_1_0 as internal_bits,__ntt_0_1_0 as ntt};}
        pub mod __internal_bits_0_1_0 {}
        pub mod __internal_type_traits_0_1_0 {}
        pub mod __modint_traits_0_1_0 {}
        pub mod __ntt_0_1_0 {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__dynamic_modint_0_1_0 as dynamic_modint,__modint_traits_0_1_0 as modint_traits,static_modint};}
        pub mod static_modint {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__internal_type_traits_0_1_0 as internal_type_traits,__modint_traits_0_1_0 as modint_traits};}
    }
}
yukicoder

結果

テストケース

ソースコード
