結果

問題 No.1847 Good Sequence
ユーザー koba-e964koba-e964
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

use std::cmp::*;
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_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-exponentiation
fn 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);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0