エクサウィザーズ 2019 E - Black or White
問題
解法
毎回 (i個目を取る時に白が無くなっている確率) + (i個目を取る時に白も黒も無くなっていない確率)/2
を出力する。 (i 個目を取る時に白が無くなっている確率) = (i-1個目を取る時に白が無くなっている確率) + (i-1個目で最後の白を取る確率)
で求まる。
コード
use mod_int::ModInt; const MOD: usize = 1e9 as usize + 7; fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let b: usize = sc.read(); let w: usize = sc.read(); let combination = Combination::new(b + w + 1, MOD); let mut inv_pow2 = vec![ModInt::new(1); b + w + 1]; inv_pow2[1] = ModInt::new(2).pow(MOD - 2); for i in 1..(b + w) { inv_pow2[i + 1] = inv_pow2[i] * inv_pow2[1]; } let mut w_zero = vec![ModInt::new(0); b + w + 1]; for i in 0..(w + b) { if i + 1 > w { w_zero[i + 1] = w_zero[i] + combination.get(i - 1, w - 1) * inv_pow2[i]; } } let mut b_zero = vec![ModInt::new(0); b + w + 1]; for i in 0..(b + w) { if i + 1 > b { b_zero[i + 1] = b_zero[i] + combination.get(i - 1, b - 1) * inv_pow2[i]; } } // eprintln!("{:?}", inv_pow2); for i in 1..(b + w + 1) { // black==0 let b_zero = if i > b { b_zero[i] } else { ModInt::new(0) }; // white==0 let w_zero = if i > w { w_zero[i] } else { ModInt::new(0) }; let other = ModInt::new(1) - b_zero - w_zero; let ans = other * inv_pow2[1] + w_zero; // eprintln!("b_zero={} w_zero={} other={}", b_zero.0, w_zero.0, other.0); println!("{}", ans.0); } } pub mod mod_int { use super::MOD; use std::ops::{Add, AddAssign, Mul, MulAssign, Sub, SubAssign}; type Num = usize; #[derive(Clone, Copy, Debug)] pub struct ModInt<T: Copy + Clone>(pub T); impl Add<ModInt<Num>> for ModInt<Num> { type Output = ModInt<Num>; fn add(self, rhs: ModInt<Num>) -> ModInt<Num> { self + rhs.0 } } impl Add<Num> for ModInt<Num> { type Output = ModInt<Num>; fn add(self, rhs: Num) -> ModInt<Num> { let mut t = rhs + self.0; if t >= MOD { t = t - MOD; } ModInt(t) } } impl Sub<Num> for ModInt<Num> { type Output = ModInt<Num>; fn sub(self, rhs: Num) -> ModInt<Num> { let rhs = if rhs >= MOD { rhs % MOD } else { rhs }; let value = if self.0 < rhs { self.0 + MOD } else { self.0 }; ModInt(value - rhs) } } impl Sub<ModInt<Num>> for ModInt<Num> { type Output = ModInt<Num>; fn sub(self, rhs: ModInt<Num>) -> ModInt<Num> { self - rhs.0 } } impl AddAssign<Num> for ModInt<Num> { fn add_assign(&mut self, other: Num) { *self = *self + other; } } impl AddAssign<ModInt<Num>> for ModInt<Num> { fn add_assign(&mut self, other: ModInt<Num>) { *self = *self + other; } } impl SubAssign<Num> for ModInt<Num> { fn sub_assign(&mut self, other: Num) { *self = *self - other; } } impl SubAssign<ModInt<Num>> for ModInt<Num> { fn sub_assign(&mut self, other: ModInt<Num>) { *self = *self - other; } } impl Mul<ModInt<Num>> for ModInt<Num> { type Output = ModInt<Num>; fn mul(self, rhs: ModInt<Num>) -> ModInt<Num> { self * rhs.0 } } impl Mul<Num> for ModInt<Num> { type Output = ModInt<Num>; fn mul(self, rhs: Num) -> ModInt<Num> { let t = (self.0 * rhs) % MOD; ModInt(t) } } impl MulAssign<Num> for ModInt<Num> { fn mul_assign(&mut self, rhs: Num) { *self = *self * rhs; } } impl MulAssign<ModInt<Num>> for ModInt<Num> { fn mul_assign(&mut self, rhs: ModInt<Num>) { *self = *self * rhs; } } impl ModInt<Num> { pub fn new(value: Num) -> Self { ModInt(value) } pub fn pow(self, e: usize) -> ModInt<Num> { let mut result = ModInt::new(1); let mut cur = self; let mut e = e; while e > 0 { if e & 1 == 1 { result *= cur; } e >>= 1; cur *= cur; } result } } } 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) -> ModInt<usize> { assert!(x >= y); ModInt::new( self.fact[x] * self.inv_fact[y] % self.modulo * self.inv_fact[x - y] % self.modulo, ) } pub fn h(&self, n: usize, r: usize) -> ModInt<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' || b == b'\r') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r') .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() } }