結果
問題 | No.3044 よくあるカエルさん |
ユーザー |
|
提出日時 | 2025-01-16 05:48:59 |
言語 | Rust (1.83.0 + proconio) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,621 bytes |
コンパイル時間 | 13,647 ms |
コンパイル使用メモリ | 400,128 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2025-01-18 00:35:07 |
合計ジャッジ時間 | 15,622 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 1 |
other | WA * 20 |
ソースコード
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<Vec<f64>>, b: &Vec<Vec<f64>>) -> Vec<Vec<f64>> { 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<Vec<f64>>, mut n: usize) -> Vec<Vec<f64>> { 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 }