結果
問題 |
No.1141 田グリッド
|
ユーザー |
![]() |
提出日時 | 2020-08-01 00:39:44 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 78 ms / 2,000 ms |
コード長 | 3,743 bytes |
コンパイル時間 | 13,448 ms |
コンパイル使用メモリ | 387,560 KB |
実行使用メモリ | 16,512 KB |
最終ジャッジ日時 | 2024-07-06 23:00:55 |
合計ジャッジ時間 | 17,424 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
use std::io::{BufRead, Write}; const MOD: usize = 1_000_000_007; fn main () { let stdin = std::io::stdin(); let stdout = std::io::stdout(); let mut reader = std::io::BufReader::new(stdin.lock()); let mut writer = std::io::BufWriter::new(stdout.lock()); let (h, w): (usize, usize) = { let mut buf = String::new(); reader.read_line(&mut buf).unwrap(); let mut iter = buf.split_whitespace(); ( iter.next().unwrap().parse().unwrap(), iter.next().unwrap().parse().unwrap(), ) }; let mut a: Vec<Vec<usize>> = Vec::with_capacity(h); for _ in 0..h { let b: Vec<usize> = { let mut buf = String::new(); reader.read_line(&mut buf).unwrap(); let iter = buf.split_whitespace(); iter.map(|x| x.parse().unwrap()).collect() }; a.push(b); } let pow = |mut a: usize, mut n: usize| -> usize { let mut res = 1; while n > 0 { if (n & 1) > 0 { res = res * a % MOD; } a = a * a % MOD; n >>= 1; } res }; let mut lu: Vec<Vec<usize>> = vec![vec![1; w]; h]; let mut ru: Vec<Vec<usize>> = vec![vec![1; w]; h]; for i in 0..h { for j in 0..w { if i > 0 { lu[i][j] = lu[i][j] * lu[i - 1][j] % MOD; } if j > 0 { lu[i][j] = lu[i][j] * lu[i][j - 1] % MOD; } if i > 0 && j > 0 { lu[i][j] = lu[i][j] * pow(lu[i - 1][j - 1], MOD - 2) % MOD; } lu[i][j] = lu[i][j] * a[i][j] % MOD; } for j in (0..w).rev() { if i > 0 { ru[i][j] = ru[i][j] * ru[i - 1][j] % MOD; } if j + 1 < w { ru[i][j] = ru[i][j] * ru[i][j + 1] % MOD; } if i > 0 && j + 1 < w { ru[i][j] = ru[i][j] * pow(ru[i - 1][j + 1], MOD - 2) % MOD; } ru[i][j] = ru[i][j] * a[i][j] % MOD; } } let mut ld: Vec<Vec<usize>> = vec![vec![1; w]; h]; let mut rd: Vec<Vec<usize>> = vec![vec![1; w]; h]; for i in (0..h).rev() { for j in 0..w { if i + 1 < h { ld[i][j] = ld[i][j] * ld[i + 1][j] % MOD; } if j > 0 { ld[i][j] = ld[i][j] * ld[i][j - 1] % MOD; } if i + 1 < h && j > 0 { ld[i][j] = ld[i][j] * pow(ld[i + 1][j - 1], MOD - 2) % MOD; } ld[i][j] = ld[i][j] * a[i][j] % MOD; } for j in (0..w).rev() { if i + 1 < h { rd[i][j] = rd[i][j] * rd[i + 1][j] % MOD; } if j + 1 < w { rd[i][j] = rd[i][j] * rd[i][j + 1] % MOD; } if i + 1 < h && j + 1 < w { rd[i][j] = rd[i][j] * pow(rd[i + 1][j + 1], MOD - 2) % MOD; } rd[i][j] = rd[i][j] * a[i][j] % MOD; } } let q: usize = { let mut buf = String::new(); reader.read_line(&mut buf).unwrap(); buf.trim_end().parse().unwrap() }; for _ in 0..q { let (r, c): (usize, usize) = { let mut buf = String::new(); reader.read_line(&mut buf).unwrap(); let mut iter = buf.split_whitespace(); ( iter.next().unwrap().parse::<usize>().unwrap() - 1, iter.next().unwrap().parse::<usize>().unwrap() - 1, ) }; let mut ans = 1; if r > 0 { if c > 0 { ans = ans * lu[r - 1][c - 1] % MOD; } if c + 1 < w { ans = ans * ru[r - 1][c + 1] % MOD; } } if r + 1 < h { if c > 0 { ans = ans * ld[r + 1][c - 1] % MOD; } if c + 1 < w { ans = ans * rd[r + 1][c + 1] % MOD; } } writeln!(writer, "{}", ans).unwrap(); } }