結果
問題 | No.2857 Div Array |
ユーザー |
![]() |
提出日時 | 2024-08-25 14:25:09 |
言語 | Rust (1.83.0 + proconio) |
結果 |
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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#![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]};}