use proconio::{input, marker::Usize1}; fn main() { input! { n: Usize1, t: usize, k: f64, l: f64, } let mut dp = vec![1.]; for i in 1..t { let mut next = 0.; if i >= 1 { next += (k - 1.) / 6. * dp[i - 1]; } if i >= 2 { next += (l - k) / 6. * dp[i - 2]; } if i >= t { next += (7. - k) / 6. * dp[i - t]; } dp.push(next); } assert_eq!(dp.len(), t); if n <= t { println!("{}", dp[n]); } let mut x = vec![vec![0.; t]; t]; x[0][0] = (k - 1.) / 6.; x[0][1] = (l - k) / 6.; x[0][t - 1] = (7. - k) / 6.; for i in 1..t { x[i][i - 1] = 1.; } let coef = pow(&x, n); let ans = coef .last() .unwrap() .iter() .zip(dp.iter().rev()) .map(|(coef, dp)| coef * dp) .fold(0., |acc, a| acc + a); println!("{}", ans); } fn multiple(a: &Vec>, b: &Vec>) -> Vec> { let n = a.len(); let mut res = vec![vec![0.; n]; n]; for i in 0..n { for j in 0..n { res[i][j] = (0..n).map(|k| a[i][k] * b[k][j]).fold(0., |acc, a| acc + a); } } res } fn pow(a: &Vec>, mut n: usize) -> Vec> { let m = a.len(); let mut res = vec![vec![0.; m]; m]; for i in 0..m { res[i][i] = 1.; } let mut base = a.clone(); while n > 0 { if n & 1 == 1 { res = multiple(&res, &base); } base = multiple(&base, &base); n >>= 1; } res }