Submission #68726727

---

Source Code Expand

#![allow(unused_imports,non_snake_case,dead_code)]
use std::{cmp::Reverse as Rev,ops::Range,collections::*,iter::*,mem::swap};
use rustc_hash::{FxHashSet as HashSet,FxHashMap as HashMap};
use ac_library::{*,modint::ModIntBase,ModInt998244353 as M};
use {proconio::{marker::*,*},itertools::*};



#[fastout]
fn main(){
    input!{
        N:usize,
        K:usize,
        X:usize,
    }

    let pre=Pre::<M>::new(500);
    let mut dp=vec![vec![[M::new(0);2];300];300];

    let ng=0;
    let ok=1;
    dp[0][0][ng]+=1;

    for i in 0..299{
        for j in 0..300{
            let [mut ngs,oks]=dp[i][j];
            if i==K{
                ngs=M::new(0);
            }

            let need=if i<K{
                j+X
            } else{
                j
            };
            let isok=i<K;

            for k in 0..=N{
                let coeff=pre.choose(N,k);
                let ngs=ngs*coeff;
                let oks=oks*coeff;
                if isok && (ngs!=M::new(0) || oks!=M::new(0)){
                    // eprintln!("i = {}",i);
                    // eprintln!("j = {}",j);
                    // eprintln!("k = {}",k);
                    // eprintln!("need = {}",need);
                    // eprintln!("ngs = {}",ngs);
                    // eprintln!("oks = {}",oks);
                    // eprintln!();
                }
                
                if k<need{
                    if (need-k)%2==0{
                        if (i+1,(need-k)/2,ok)==(1,0,1){
                            // eprintln!("a: {}",ngs+oks);
                        }
                        dp[i+1][(need-k)/2][ok]+=ngs+oks;
                    } else{
                        if isok{
                            if (i+1,(need-k+1)/2,ng)==(1,0,1){
                                // eprintln!("b: {}",ngs);
                            }
                            dp[i+1][(need-k+1)/2][ng]+=ngs;
                            if (i+1,(need-k+1)/2,ok)==(1,0,1){
                                // eprintln!("x: {}",oks);
                            }
                            dp[i+1][(need-k+1)/2][ok]+=oks;
                        }
                    }
                } else if k==need{
                    if (i+1,0,ok)==(1,0,1){
                        // eprintln!("c: {}",ngs+oks);
                    }
                    dp[i+1][0][ok]+=ngs+oks;
                } else if k==need+1{
                    if isok{
                        if (i+1,0,ng)==(1,0,1){
                            // eprintln!("d: {}",ngs);
                        }
                        dp[i+1][0][ng]+=ngs;
                        if (i+1,0,ok)==(1,0,1){
                            // eprintln!("e: {}",oks);
                        }
                        dp[i+1][0][ok]+=oks;
                    }
                } else{
                    if isok{
                        if (i+1,0,ng)==(1,0,1){
                            // eprintln!("f: {}",ngs+oks);
                        }
                        dp[i+1][0][ng]+=ngs+oks;
                    }
                }
            }
        }
    }

    // for i in 0..5{
    //     for j in 0..5{
    //         eprint!("{:?} ",dp[i][j]);
    //     }
    //     // eprintln!();
    // }

    let ans=dp[299][0][ok];
    println!("{ans}");
}



// Modを超える数はpanicする
// 注意：
//      Modは素数
//      multi_choose(n,k)を使うときは，fac(n+k-1)まで必要になる
struct Pre<M:ModIntBase>{
    fac:Vec<M>,
    finv:Vec<M>,
}
impl<M:ModIntBase> Pre<M>{
    fn new(n:usize)->Self{
        assert!(n<M::modulus() as usize);

        let mut fac=vec![M::new(1);n+1];
        for i in 1..=n{
            fac[i]=fac[i-1]*M::new(i);
        }

        let mut finv=vec![M::new(0);n+1];
        finv[n]=fac[n].inv();
        for i in (1..=n).rev(){
            finv[i-1]=finv[i]*M::new(i);
        }
        
        Self{fac,finv}
    }

    fn fac(&self,n:usize)->M{
        self.fac[n]
    }

    fn finv(&self,n:usize)->M{
        self.finv[n]
    }

    fn inv(&self,n:usize)->M{
        assert!(n!=0);
        self.finv[n]*self.fac[n-1]
    }

    fn perm(&self,n:usize,k:usize)->M{
        if n<k || (n as i64)<0 || (k as i64)<0{
            return M::new(0);
        }
        self.fac(n)*self.finv(n-k)
    }

    fn choose(&self,n:usize,k:usize)->M{
        if n<k || (n as i64)<0 || (k as i64)<0{
            return M::new(0);
        }
        self.fac(n)*self.finv(k)*self.finv(n-k)
    }

    fn multi_choose(&self,n:usize,k:usize)->M{
        if (n as i64)<0 || (k as i64)<0{
            return M::new(0);
        }
        if n==0 && k==0{
            return M::new(1);
        }
        self.choose(n+k-1,k)
    }
}

Submission Info

Judge Result