結果

問題 No.3002 多項式の割り算 〜easy〜
コンテスト
ユーザー maysay_d
提出日時 2025-01-17 21:34:51
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 1,271 bytes
コンパイル時間 13,336 ms
コンパイル使用メモリ 401,912 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2025-01-17 21:35:49
合計ジャッジ時間 14,540 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other AC * 3 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#![allow(unused_imports)]
#![allow(unused_variables)]
#![allow(non_snake_case)]
use proconio::input;
use proconio::marker::*;
use std::cmp::*;
use std::collections::*;

const MOD: i64 = 1_000_000_007;

fn main() {
    input! {
        A: i64,
        B: usize,
    }

    let (a, b) = solve(A, B);

    println!("{} {}", a, b);
}

fn solve(A: i64, B: usize) -> (i64, i64) {
    const VEC: [i64; 3] = [1, 1, 1];
    
    let mut current = vec![0, 0, 1];

    let mut power = B;
    let mut result = vec![1, 0, 0];

    while power > 0 {
        if power % 2 == 1 {
            result = mul(&result, &current, &VEC);
        }
        current = mul(&current, &current, &VEC);
        power /= 2;
    }

    let result = result.iter().map(|&x| (x * A) % MOD).collect::<Vec<_>>();

    let a = result[1];
    let b = result[0];

    (a, b)
}

fn mul(f1: &[i64], f2: &[i64], vec: &[i64]) -> Vec<i64> {
    let mut result = vec![0; 5];

    for i in 0..f1.len() {
        for j in 0..f2.len() {
            result[i + j] += f1[i] * f2[j];
        }
    }

    for i in (3..result.len()).rev() {
        for j in 0..3 {
            result[i - 3 + j] -= result[i] * vec[j];
        }
    }

    result.truncate(3);

    result.iter().map(|&x| ((x % MOD) + MOD) % MOD).collect()
}
0