Submission #25616347

---

Source Code Expand

//! # Bundled libraries
//!
//! - `ext_gcd 0.1.0 (git+https://github.com/ia7ck/rust-competitive-programming#b386c09337c49e3879ca0d599676e9d83609d32a)`       licensed under **missing** as `crate::__cargo_equip::crates::__ext_gcd_0_1_0`
//! - `mod_int 0.1.0 (git+https://github.com/ia7ck/rust-competitive-programming#b386c09337c49e3879ca0d599676e9d83609d32a)`       licensed under **missing** as `crate::__cargo_equip::crates::mod_int`
//! - `procon_reader 0.1.0 (git+https://github.com/ia7ck/rust-competitive-programming#b386c09337c49e3879ca0d599676e9d83609d32a)` licensed under **missing** as `crate::__cargo_equip::crates::procon_reader`

pub use __cargo_equip::prelude::*;

use std::collections::HashMap;

use mod_int::ModInt998244353;
use procon_reader::ProconReader;
type Mint = ModInt998244353;

fn solve(
    l: usize,
    r: usize,
    ok: &Vec<Vec<bool>>,
    cmb: &Vec<Vec<Mint>>,
    memo: &mut HashMap<(usize, usize), Mint>,
) -> Mint {
    if l == r {
        return Mint::new(1);
    }
    if let Some(&ans) = memo.get(&(l, r)) {
        return ans;
    }
    let mut ans = Mint::new(0);
    // make pair (l, i)
    for i in ((l + 1)..r).step_by(2) {
        if ok[l][i] {
            // [l+1, i), [i+1, r)
            let l_val = solve(l + 1, i, ok, cmb, memo);
            let r_val = solve(i + 1, r, ok, cmb, memo);
            ans += l_val * r_val * cmb[(r - l) / 2][(r - (i + 1)) / 2];
        }
    }
    memo.insert((l, r), ans);
    ans
}

fn main() {
    let stdin = std::io::stdin();
    let mut rd = ProconReader::new(stdin.lock());

    let n: usize = rd.get();
    let m: usize = rd.get();
    let mut ok = vec![vec![false; n * 2]; n * 2];
    for _ in 0..m {
        let a: usize = rd.get();
        let b: usize = rd.get();
        ok[a - 1][b - 1] = true;
        ok[b - 1][a - 1] = true;
    }

    let mut cmb = vec![vec![Mint::new(0); n + 1]; n + 1];
    cmb[0][0] = Mint::new(1);
    for i in 1..=n {
        cmb[i][0] = Mint::new(1);
        for j in 1..=i {
            cmb[i][j] = cmb[i - 1][j - 1] + cmb[i - 1][j];
        }
    }
    let mut memo = HashMap::new();
    let ans = solve(0, n * 2, &ok, &cmb, &mut memo);
    println!("{}", ans.val());
}

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

#[rustfmt::skip]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod __ext_gcd_0_1_0 {#[allow(clippy::many_single_char_names)]pub fn ext_gcd(a:i64,b:i64)->(i64,i64,i64){if b==0{if a==0{(0,0,0)}else{(1,0,a)}}else{let(q,r)=(a/b,a%b);let(s,t,g)=ext_gcd(b,r);(t,s-q*t,g)}}}
        pub mod mod_int {use crate::__cargo_equip::preludes::mod_int::*;pub use crate::__cargo_equip::macros::mod_int::*;use std::convert::TryInto;use std::fmt::Debug;use std::marker::PhantomData;use std::ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Sub,SubAssign};use ext_gcd::ext_gcd;pub trait Modulo:Copy+Clone+Debug{const P:i64;}#[derive(Copy,Clone,Debug)]pub struct ModInt<M>(i64,PhantomData<M>);impl<M:Modulo>ModInt<M>{pub fn new(x:i64)->Self{if 0<=x&&x<M::P{Self::new_raw(x)}else{Self::new_raw(x.rem_euclid(M::P))}}fn new_raw(x:i64)->Self{debug_assert!(0<=x&&x<M::P);Self(x,PhantomData)}pub fn val(self)->i64{self.0}pub fn p()->i64{M::P}pub fn pow<T>(self,exp:T)->Self where T:TryInto<u64>,<T as TryInto<u64> >::Error:Debug,{let mut res=1;let mut base=self.0;let mut exp=exp.try_into().unwrap();while exp>0{if exp&1==1{res*=base;res%=M::P;}base*=base;base%=M::P;exp>>=1;}Self::new_raw(res)}pub fn inv(self)->Self{assert_ne!(self.0,0,"Don't divide by zero!");let(x,_,g)=ext_gcd(self.0,M::P);assert_eq!(g,1,"{} is not prime!",M::P);Self::new(x)}}impl<M:Modulo,T:Into<ModInt<M> > >AddAssign<T>for ModInt<M>{fn add_assign(&mut self,rhs:T){self.0+=rhs.into().0;debug_assert!(0<=self.0&&self.0<=(M::P-1)*2);if self.0>=M::P{self.0-=M::P;}}}impl<M:Modulo,T:Into<ModInt<M> > >Add<T>for ModInt<M>{type Output=ModInt<M>;fn add(self,rhs:T)->Self::Output{let mut result=self;result+=rhs.into();result}}impl<M:Modulo,T:Into<ModInt<M> > >SubAssign<T>for ModInt<M>{fn sub_assign(&mut self,rhs:T){self.0-=rhs.into().0;debug_assert!(-(M::P-1)<=self.0&&self.0<M::P);if self.0<0{self.0+=M::P;}}}impl<M:Modulo,T:Into<ModInt<M> > >Sub<T>for ModInt<M>{type Output=ModInt<M>;fn sub(self,rhs:T)->Self::Output{let mut result=self;result-=rhs.into();result}}impl<M:Modulo,T:Into<ModInt<M> > >MulAssign<T>for ModInt<M>{fn mul_assign(&mut self,rhs:T){self.0*=rhs.into().0;if self.0>=M::P{self.0%=M::P;}}}impl<M:Modulo,T:Into<ModInt<M> > >Mul<T>for ModInt<M>{type Output=ModInt<M>;fn mul(self,rhs:T)->Self::Output{let mut result=self;result*=rhs.into();result}}impl<M:Modulo,T:Into<ModInt<M> > >DivAssign<T>for ModInt<M>{fn div_assign(&mut self,rhs:T){*self*=rhs.into().inv();}}impl<M:Modulo,T:Into<ModInt<M> > >Div<T>for ModInt<M>{type Output=ModInt<M>;fn div(self,rhs:T)->Self::Output{let mut result=self;result/=rhs.into();result}}macro_rules!impl_from_int{($($t:ty),+)=>{$(impl<M:Modulo>From<$t>for ModInt<M>{fn from(x:$t)->Self{Self::new(x as i64)}})+};}impl_from_int!(i32,i64,u32);macro_rules!impl_from_large_int{($($t:ty),+)=>{$(impl<M:Modulo>From<$t>for ModInt<M>{fn from(x:$t)->Self{Self::new((x%(M::P as$t))as i64)}})+};}impl_from_large_int!(u64,usize);define_mod_int_p!(Mod1000000007,ModInt1000000007,1_000_000_000+7);define_mod_int_p!(Mod998244353,ModInt998244353,998_244_353);}
        pub mod procon_reader {use std::io::BufRead;use std::str::FromStr;pub struct ProconReader<R>{r:R,l:String,i:usize,}impl<R:BufRead>ProconReader<R>{pub fn new(reader:R)->Self{Self{r:reader,l:String::new(),i:0,}}pub fn get<T>(&mut self)->T where T:FromStr,<T as FromStr>::Err:std::fmt::Debug,{self.skip_blanks();assert!(self.i<self.l.len());assert_ne!(&self.l[self.i..=self.i]," ");let rest=&self.l[self.i..];let len=rest.find(' ').unwrap_or_else(| |rest.len());let val=rest[..len].parse().unwrap_or_else(|e|panic!("{:?}, attempt to read `{}`",e,rest));self.i+=len;val}fn skip_blanks(&mut self){loop{match self.l[self.i..].find(|ch|ch!=' '){Some(j)=>{self.i+=j;break;}None=>{let mut buf=String::new();let num_bytes=self.r.read_line(&mut buf).unwrap_or_else(|_|panic!("invalid UTF-8"));assert!(num_bytes>0,"reached EOF :(");self.l=buf.trim_end_matches('\n').trim_end_matches('\r').to_string();self.i=0;}}}}pub fn get_vec<T>(&mut self,n:usize)->Vec<T>where T:FromStr,<T as FromStr>::Err:std::fmt::Debug,{(0..n).map(|_|self.get()).collect()}pub fn get_chars(&mut self)->Vec<char>{self.get::<String>().chars().collect()}}}
    }

    pub(crate) mod macros {
        pub mod __ext_gcd_0_1_0 {}
        pub mod mod_int {pub use crate::__macro_def_mod_int_define_mod_int_p as define_mod_int_p;}
        pub mod procon_reader {}
    }

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

    mod preludes {
        pub mod __ext_gcd_0_1_0 {}
        pub mod mod_int {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::__ext_gcd_0_1_0 as ext_gcd;}
        pub mod procon_reader {}
    }
}

#[cfg_attr(any(), rustfmt::skip)]
const _: () = {
    #[macro_export] macro_rules! __macro_def_mod_int_define_mod_int_p(($mod:ident,$mod_int:ident,$p:expr)=>{#[derive(Clone,Copy,Debug)]pub struct$mod;impl Modulo for$mod{const P:i64=$p;}pub type$mod_int=ModInt<$mod>;};);
};

Submission Info

Judge Result