結果

問題 No.3045 反復重み付き累積和
ユーザー titia
提出日時 2025-03-06 03:01:39
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 2,141 bytes
コンパイル時間 13,516 ms
コンパイル使用メモリ 394,876 KB
実行使用メモリ 41,888 KB
最終ジャッジ日時 2025-03-06 03:02:02
合計ジャッジ時間 20,716 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 4 TLE * 1 -- * 36
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused variable: `i`
  --> src/main.rs:58:13
   |
58 |         for i in 1..=n {
   |             ^ help: if this is intentional, prefix it with an underscore: `_i`
   |
   = note: `#[warn(unused_variables)]` on by default

ソースコード

diff # 

use std::io;

const MOD: i64 = 998244353;

fn mod_pow(base: i64, exp: i64, modulus: i64) -> i64 {
    let mut result = 1;
    let mut base = base % modulus;
    let mut exp = exp;
    while exp > 0 {
        if exp % 2 == 1 {
            result = result * base % modulus;
        }
        base = base * base % modulus;
        exp /= 2;
    }
    result
}

fn prod(a: &Vec<Vec<i64>>, b: &Vec<Vec<i64>>, k: usize, l: usize, m: usize) -> Vec<Vec<i64>> {
    let mut c = vec![vec![0; m]; k];
    for i in 0..k {
        for j in 0..m {
            let mut ans = 0;
            for pl in 0..l {
                ans = (ans + a[i][pl] * b[pl][j]) % MOD;
            }
            c[i][j] = ans;
        }
    }
    c
}

fn main() {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let nums: Vec<usize> = input.trim().split_whitespace().map(|x| x.parse().unwrap()).collect();
    let (n, q) = (nums[0], nums[1]);

    input.clear();
    io::stdin().read_line(&mut input).unwrap();
    let mut a: Vec<Vec<i64>> = vec![input.trim().split_whitespace().map(|x| x.parse().unwrap()).collect()];

    for _ in 0..q {
        input.clear();
        io::stdin().read_line(&mut input).unwrap();
        let l: Vec<i64> = input.trim().split_whitespace().map(|x| x.parse().unwrap()).collect();
        
        if l[0] == 2 {
            let x = (l[1] - 1) as usize;
            println!("{}", a[0][x]);
            continue;
        }
        
        let (k, x) = (l[1], l[2]);
        let mut l_vec = vec![1i64];
        let (mut bunshi, mut bunbo) = (x, 1);
        
        for i in 1..=n {
            let now = *l_vec.last().unwrap();
            l_vec.push(now * k * bunshi % MOD * mod_pow(bunbo, MOD - 2, MOD) % MOD);
            bunshi += 1;
            bunbo += 1;
        }
        
        let mut x_mat = vec![vec![0; n]; n];
        for i in 0..n {
            for j in 0..n {
                if i + j < n {
                    x_mat[i][i + j] = l_vec[j];
                } else {
                    break;
                }
            }
        }
        
        a = prod(&a, &x_mat, 1, n, n);
    }
}
0