#1136292 (Rust) No.435 占い(Extra)

• 問題: No.435 占い(Extra)
• ユーザー: cologne
• 提出日時: 2025-11-25 14:13:03
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 179 ms / 2,000 ms
• コード長: 4,214 bytes
• コンパイル時間: 12,177 ms
• コンパイル使用メモリ: 399,744 KB
• 実行使用メモリ: 7,720 KB
• 最終ジャッジ日時: 2025-11-25 14:13:20
• 合計ジャッジ時間: 16,354 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

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

ソースコード

use fio::*;

const INV_9: [u8; 9] = [0, 1, 5, 0, 7, 2, 0, 4, 8];

fn solve(mut rng: impl ExactSizeIterator<Item = u8>) -> u8 {
    let n = rng.len();
    let mut upper_mod_9 = 1;
    let mut upper_pow_3 = 0;
    let mut lower_mod_9 = 1;
    let mut lower_pow_3 = 0;

    let split = |mut x: usize| -> (u8, usize) {
        let mut pow_3 = 0;
        while x % 3 == 0 {
            x /= 3;
            pow_3 += 1;
        }
        ((x % 9) as u8, pow_3)
    };

    let augment = |mod9: &mut u8, pow_3: &mut usize, x: usize| {
        let (x_mod_9, x_pow_3) = split(x);
        *mod9 *= x_mod_9;
        *mod9 %= 9;
        *pow_3 += x_pow_3;
    };

    let v = rng.next().unwrap();
    let mut is_ans_0 = v == 0;
    let mut ans = v % 9;

    for i in 1..=n - 1 {
        augment(&mut upper_mod_9, &mut upper_pow_3, n - i);
        augment(&mut lower_mod_9, &mut lower_pow_3, i);
        let v = rng.next().unwrap();

        if v != 0 {
            is_ans_0 = false;
        }

        let mut m9 = upper_mod_9 * INV_9[lower_mod_9 as usize] % 9;
        let p3 = upper_pow_3 - lower_pow_3;

        if p3 == 1 {
            m9 = m9 * 3 % 9;
        }
        if p3 <= 1 {
            ans = (ans + v * m9) % 9;
        }
    }

    if is_ans_0 {
        0
    } else if ans == 0 {
        9
    } else {
        ans
    }
}

fn main() {
    let t = read();
    for _ in 0..t {
        let [n, x, a, b, m] = read_tuple::<usize, 5>();
        struct RNG {
            n: usize,
            x: usize,
            a: usize,
            b: usize,
            m: usize,
        }
        impl Iterator for RNG {
            type Item = u8;

            fn next(&mut self) -> Option<Self::Item> {
                if self.n == 0 {
                    None
                } else {
                    let ret = (self.x % 10) as u8;
                    self.n -= 1;
                    self.x = ((self.x ^ self.a) + self.b) % self.m;
                    Some(ret)
                }
            }

            fn size_hint(&self) -> (usize, Option<usize>) {
                (self.n, Some(self.n))
            }
        }
        impl ExactSizeIterator for RNG {
            fn len(&self) -> usize {
                self.n
            }
        }

        let rng = RNG { n, x, a, b, m };
        println!("{}", solve(rng));
    }
}

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()
        });
    };
}