AtCoder Beginner Contest 132 D - Blue and Red Balls
問題
解法
K個の青いボールをi個の区間に分け、かつ、全ての区間が1個以上ボールを含むような青いボールの分け方は である。同様に考えて赤いボールの分け方を求め、この2つの積が答えになる。
const MOD: usize = 1e9 as usize + 7; fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let n: usize = sc.read(); let blue_ball: usize = sc.read(); let c = Combination::new(n * 2 + 1, MOD); let red_ball = n - blue_ball; for seg in 1..(blue_ball + 1) { if seg > blue_ball || seg - 1 > red_ball { println!("0"); continue; } let free_blue = blue_ball - seg; let free_red = red_ball - (seg - 1); let ans = c.get(free_blue + seg - 1, free_blue) * c.get(free_red + seg + 1 - 1, free_red); println!("{}", ans % MOD); } } pub struct Combination { fact: Vec<usize>, inv_fact: Vec<usize>, modulo: usize, } impl Combination { pub fn new(max: usize, modulo: usize) -> Combination { let mut inv = vec![0; max + 1]; let mut fact = vec![0; max + 1]; let mut inv_fact = vec![0; max + 1]; inv[1] = 1; for i in 2..(max + 1) { inv[i] = inv[modulo % i] * (modulo - modulo / i) % modulo; } fact[0] = 1; inv_fact[0] = 1; for i in 0..max { fact[i + 1] = fact[i] * (i + 1) % modulo; } for i in 0..max { inv_fact[i + 1] = inv_fact[i] * inv[i + 1] % modulo; } Combination { fact: fact, inv_fact: inv_fact, modulo: modulo, } } pub fn get(&self, x: usize, y: usize) -> usize { assert!(x >= y); self.fact[x] * self.inv_fact[y] % self.modulo * self.inv_fact[x - y] % self.modulo } pub fn h(&self, n: usize, r: usize) -> usize { self.get(n + r - 1, r) } } pub struct Scanner<R> { stdin: R, } impl<R: std::io::Read> Scanner<R> { pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .stdin .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n') .take_while(|&b| b != b' ' && b != b'\n') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }