結果
問題 | No.2857 Div Array |
ユーザー | QiToY |
提出日時 | 2024-08-25 14:25:09 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 32 ms / 2,000 ms |
コード長 | 2,268 bytes |
コンパイル時間 | 13,042 ms |
コンパイル使用メモリ | 405,424 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-08-25 14:25:24 |
合計ジャッジ時間 | 12,986 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,812 KB |
testcase_02 | AC | 1 ms
6,940 KB |
testcase_03 | AC | 1 ms
6,944 KB |
testcase_04 | AC | 1 ms
6,940 KB |
testcase_05 | AC | 1 ms
6,940 KB |
testcase_06 | AC | 1 ms
6,940 KB |
testcase_07 | AC | 1 ms
6,944 KB |
testcase_08 | AC | 1 ms
6,944 KB |
testcase_09 | AC | 1 ms
6,940 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 25 ms
6,940 KB |
testcase_12 | AC | 7 ms
6,940 KB |
testcase_13 | AC | 2 ms
6,944 KB |
testcase_14 | AC | 23 ms
6,948 KB |
testcase_15 | AC | 3 ms
6,940 KB |
testcase_16 | AC | 1 ms
6,940 KB |
testcase_17 | AC | 21 ms
6,944 KB |
testcase_18 | AC | 19 ms
6,940 KB |
testcase_19 | AC | 10 ms
6,944 KB |
testcase_20 | AC | 31 ms
6,944 KB |
testcase_21 | AC | 31 ms
6,944 KB |
testcase_22 | AC | 32 ms
6,940 KB |
testcase_23 | AC | 31 ms
6,944 KB |
testcase_24 | AC | 1 ms
6,944 KB |
testcase_25 | AC | 1 ms
6,940 KB |
testcase_26 | AC | 1 ms
6,940 KB |
testcase_27 | AC | 1 ms
6,940 KB |
testcase_28 | AC | 0 ms
6,944 KB |
testcase_29 | AC | 1 ms
6,944 KB |
ソースコード
#![allow(unused_imports)] fn main() { input! { n: u64, m: usize, k: usize, } let mut cnt = vec![0; m + 1]; for i in 1..=m { cnt[m / i] += 1; } let mut nonzero = vec![]; for (i, c) in cnt.into_iter().enumerate() { if c != 0 { nonzero.push((i, c)); } } let l = nonzero.len(); let mut mat = mvec![0; (l, l)]; for (i, &(d, c)) in nonzero.iter().enumerate() { for (j, &(dd, _)) in nonzero.iter().enumerate() { if d.abs_diff(dd) <= k { mat[i][j] += c; } } } mat = mat_pow(mat, n - 1); let mut ans = 0; for i in 0..l { for j in 0..l { ans += mat[i][j] * nonzero[j].1; ans %= MOD; } } println!("{ans}"); } fn mat_prod(a: &[Vec<u64>], b: &[Vec<u64>]) -> Vec<Vec<u64>> { let n = a.len(); let mut c = mvec![0; (n, n)]; for i in 0..n { for k in 0..n { for j in 0..n { c[i][j] += a[i][k] * b[k][j]; c[i][j] %= MOD; } } } c } fn mat_pow(mut a: Vec<Vec<u64>>, mut p: u64) -> Vec<Vec<u64>> { let n = a.len(); let mut r = mvec![0; (n, n)]; for i in 0..n { r[i][i] += 1; } while p > 0 { if p & 1 == 1 { r = mat_prod(&r, &a); } a = mat_prod(&a, &a); p >>= 1; } r } const MOD: u64 = 998244353; /* dp[i+1][a] = cnt[a] * (dp[i][a-38] + .. + dp[i][a+38]) non zero value => O(sqrt m) 2 3 1 [0, 2, 0, 1] [0, 4, 0, 1] */ use proconio::{input, marker::*}; use std::{cmp::Reverse, collections::*}; #[macro_export] macro_rules! chmax { ($a:expr, $b:expr) => {{ let tmp = $b; if $a < tmp { $a = tmp; true } else { false } }}; } #[macro_export] macro_rules! chmin { ($a:expr, $b:expr) => {{ let tmp = $b; if $a > tmp { $a = tmp; true } else { false } }}; } #[macro_export] /// mvec![] macro_rules! mvec { ($val:expr; ()) => { $val }; ($val:expr; ($size:expr $(,$rest:expr)*)) => { vec![mvec![$val; ($($rest),*)]; $size] }; }