#1145345 (Rust) No.147 試験監督（2）

• 問題: No.147 試験監督（2）
• ユーザー: cologne
• 提出日時: 2026-01-22 17:32:02
• 言語: Rust (1.92.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 299 ms / 2,000 ms
• コード長: 4,006 bytes
• コンパイル時間: 27,993 ms
• コンパイル使用メモリ: 416,356 KB
• 実行使用メモリ: 7,852 KB
• 最終ジャッジ日時: 2026-01-22 17:33:42
• 合計ジャッジ時間: 30,708 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

ファイルパターン	結果
other	AC * 4

ソースコード

use fio::*;
use std::ops::Mul;

const MOD: u32 = 1_000_000_007;

#[derive(Copy, Clone)]
struct Mat {
    _00: u32,
    _01: u32,
    _10: u32,
    _11: u32,
}

impl Mul for Mat {
    type Output = Self;

    fn mul(self, rhs: Self) -> Self::Output {
        let (a00, a01, a10, a11) = (
            self._00 as u64,
            self._01 as u64,
            self._10 as u64,
            self._11 as u64,
        );
        let (b00, b01, b10, b11) = (
            rhs._00 as u64,
            rhs._01 as u64,
            rhs._10 as u64,
            rhs._11 as u64,
        );
        let (c00, c01, c10, c11) = (
            a00 * b00 + a01 * b10,
            a00 * b01 + a01 * b11,
            a10 * b00 + a11 * b10,
            a10 * b01 + a11 * b11,
        );
        Self {
            _00: (c00 % MOD as u64) as u32,
            _01: (c01 % MOD as u64) as u32,
            _10: (c10 % MOD as u64) as u32,
            _11: (c11 % MOD as u64) as u32,
        }
    }
}

fn pow(m: Mat, b: u64) -> Mat {
    if b == 0 {
        Mat {
            _00: 1,
            _01: 0,
            _10: 0,
            _11: 1,
        }
    } else if b % 2 == 1 {
        m * pow(m, b - 1)
    } else {
        let r = pow(m, b / 2);
        r * r
    }
}

fn powmod(a: u32, b: u64) -> u32 {
    if b == 0 {
        1
    } else if b % 2 == 1 {
        (a as u64 * powmod(a, b - 1) as u64 % MOD as u64) as u32
    } else {
        let r = powmod(a, b / 2);
        (r as u64 * r as u64 % MOD as u64) as u32
    }
}

const FIB: Mat = Mat {
    _00: 1,
    _01: 1,
    _10: 1,
    _11: 0,
};

fn solve(c: u64, d: &str) -> u32 {
    let val = pow(FIB, 1 + c)._00;
    let mut ans = 1u32;
    for c in d.chars().map(|x| x.to_digit(10).unwrap()) {
        ans = powmod(ans, 10);
        ans = (ans as u64 * powmod(val, c as u64) as u64 % MOD as u64) as u32
    }
    ans
}

fn main() {
    let n = read();
    let mut ans = 1u32;
    for _ in 0..n {
        let [c, d] = read_tuple::<String, 2>();
        let r = solve(c.parse().unwrap(), &d);
        ans = (ans as u64 * r as u64 % MOD as u64) as u32;
    }
    println!("{ans}")
}

mod fio {
    use std::{
        cell::RefCell,
        convert::TryInto,
        fmt::Debug,
        io::{BufRead, BufWriter, StdinLock, StdoutLock, stdin, stdout},
        str::FromStr,
    };
    thread_local! {
        pub static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());
        pub static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> = RefCell::new(BufWriter::new(stdout().lock()));
    }

    #[allow(dead_code)]
    pub fn read<T: FromStr>() -> T
    where
        <T as FromStr>::Err: Debug,
    {
        read_line().parse().unwrap()
    }

    #[allow(dead_code)]
    pub fn read_vec<T: FromStr>() -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        read_line()
            .split_whitespace()
            .map(|x| x.parse().unwrap())
            .collect()
    }

    #[allow(dead_code)]
    pub fn read_tuple<T, const N: usize>() -> [T; N]
    where
        T: FromStr + Debug,
        <T as FromStr>::Err: Debug,
    {
        read_vec::<T>().try_into().unwrap()
    }

    /// whitespace at the end of the line is ignored
    pub fn read_line() -> String {
        let mut s = String::new();
        STDIN.with(|cell| {
            cell.borrow_mut().read_line(&mut s).unwrap();
        });
        String::from_str(s.trim_end()).unwrap()
    }
}

#[macro_export]
macro_rules! print {
    ($($t:tt)*) => {
        fio::STDOUT.with(|cell|{
            use std::io::Write;
            write!(cell.borrow_mut(), $($t)*).unwrap()
        })};
}

#[macro_export]
macro_rules! println {
    ($($t:tt)*) => {
        fio::STDOUT.with(|cell| {
            use std::io::Write;
            writeln!(cell.borrow_mut(), $($t)*).unwrap()
        })
    };
}

#[macro_export]
macro_rules! flush {
    () => {
        fio::STDOUT.with(|cell| {
            use std::io::Write;
            cell.borrow_mut().flush().unwrap()
        });
    };
}