結果

問題 No.3404 形式群法則
コンテスト
ユーザー koba-e964
提出日時 2025-12-15 13:29:47
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 246 ms / 2,000 ms
コード長 1,387 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 13,505 ms
コンパイル使用メモリ 398,708 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-12-15 13:30:03
合計ジャッジ時間 14,987 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

fn getline() -> String {
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).unwrap();
    ret
}

fn op(a: &[i64], b: &[i64], p: i64) -> Vec<i64> {
    let n = a.len();
    let mut num = vec![0; n];
    let mut den = vec![0; n];
    for i in 0..n {
        num[i] = (a[i] + b[i]) % p;
        for j in 0..n - i {
            den[i + j] = (den[i + j] + a[i] * b[j]) % p;
        }
    }
    let mut ans = vec![0; n];
    for i in 0..n {
        let l = num[i];
        ans[i] = l;
        for j in 2..n - i {
            num[i + j] = (num[i + j] + l * den[j]) % p;
        }
    }
    ans
}

fn pow(a: &[i64], mut e: i64, p: i64) -> Vec<i64> {
    let n = a.len();
    let mut cur = a.to_vec();
    let mut prod = vec![0; n];
    while e > 0 {
        if e % 2 != 0 {
            prod = op(&cur, &prod, p);
        }
        cur = op(&cur, &cur, p);
        e /= 2;
    }
    prod
}

fn main() {
    let ints = getline().trim().split_whitespace()
        .map(|x| x.parse::<i64>().unwrap())
        .collect::<Vec<_>>();
    let [n, m, p] = ints[..] else { panic!() };
    let n = n as usize;
    let mut a = getline().trim().split_whitespace()
        .map(|x| x.parse::<i64>().unwrap() % p)
        .collect::<Vec<_>>();
    a.insert(0, 0);
    let res = pow(&a, m, p);
    for i in 1..=n {
        print!("{}{}", res[i], if i == n { "\n" } else { " " });
    }
}
0