結果
問題 | No.1847 Good Sequence |
ユーザー |
|
提出日時 | 2022-02-20 13:48:29 |
言語 | Rust (1.83.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,475 bytes |
コンパイル時間 | 14,291 ms |
コンパイル使用メモリ | 378,820 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-29 10:47:37 |
合計ジャッジ時間 | 15,805 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 6 WA * 35 |
ソースコード
use std::cmp::*;// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8macro_rules! input {($($r:tt)*) => {let stdin = std::io::stdin();let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));let mut next = move || -> String{bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect()};input_inner!{next, $($r)*}};}macro_rules! input_inner {($next:expr) => {};($next:expr,) => {};($next:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($next, $t);input_inner!{$next $($r)*}};}macro_rules! read_value {($next:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()};($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error"));}// Registry.#[derive(Clone, Default, Debug)]struct Reg<T> {a: Vec<T>,inv: std::collections::HashMap<T, usize>,}impl<T: Default> Reg<T> {pub fn new() -> Self {Self::default()}}impl<T: std::hash::Hash + Eq + Clone> Reg<T> {pub fn get(&mut self, t: &T) -> usize {if !self.inv.contains_key(t) {let idx = self.a.len();self.a.push(t.clone());self.inv.insert(t.clone(), idx);}self.inv[t]}// init must have distinct elements.pub fn init<F>(&mut self, init: &[T], f: F) -> Vec<Vec<i64>>where F: Fn(T) -> Vec<T> {let mut que = std::collections::VecDeque::new();for t in init {let idx = self.get(t);que.push_back(idx);}let mut n = self.a.len();let mut vis = vec![false; n];let mut to = vec![vec![]; n];while let Some(v) = que.pop_front() {if vis[v] { continue; }let ans = f(self.a[v].clone());let mut entries = vec![];for elem in ans {let idx = self.get(&elem);entries.push(idx);if n <= idx {// A newly created entry.n = self.a.len();vis.resize(n, false);to.resize(n, vec![]);que.push_back(idx);}}vis[v] = true;to[v] = entries;}let mut ans = vec![vec![0; n]; n];for i in 0..n {for &e in &to[i] {ans[i][e] += 1;}}ans}}fn squmul(a: &[Vec<i64>], b: &[Vec<i64>], mo: i64) -> Vec<Vec<i64>> {let n = a.len();let mut ret = vec![vec![0; n]; n];for i in 0..n {for j in 0..n {for k in 0..n {ret[i][k] += a[i][j] * b[j][k];ret[i][k] %= mo;}}}ret}fn squpow(a: &[Vec<i64>], mut e: i64, mo: i64) -> Vec<Vec<i64>> {let n = a.len();let mut sum = vec![vec![0; n]; n];for i in 0..n { sum[i][i] = 1; }let mut cur = a.to_vec();while e > 0 {if e % 2 == 1 {sum = squmul(&sum, &cur, mo);}cur = squmul(&cur, &cur, mo);e /= 2;}sum}const MOD: i64 = 1_000_000_007;// Tags: matrix-exponentiationfn main() {input! {l: i64, n: usize, m: usize,k: [usize; m],}let mut pop = vec![false; n];for k in k {pop[k - 1] = true;}let mut reg = Reg::new();reg.get(&(-2, -2));for i in 0..n as i32 {if pop[i as usize] {reg.get(&(i, i));}}let init = (-1, -1);let next = |(x, y)| -> Vec<(i32, i32)> {if (x, y) == (-2, -2) {return vec![(-2, -2); n];}let mut v = vec![];for i in 0..n as i32 {if x == i {v.push((x, min(n as i32, y + 1)));} else if x >= 0 && x == y && pop[x as usize] {v.push((-2, -2));} else {v.push((i, 0));}}v};let mat = reg.init(&[init], next);let pw = squpow(&mat, l, MOD);let mut tot = pw[0][reg.get(&(-2, -2))];for i in 0..n as i32 {if pop[i as usize] {tot += pw[0][reg.get(&(i, i))];tot %= MOD;}}println!("{}", tot);}