#1150201 (Rust) No.3457 Fibo-shrink

• 問題: No.3457 Fibo-shrink
• ユーザー: elphe
• 提出日時: 2026-02-28 14:24:54
• 言語: Rust (1.93.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 18 ms / 2,000 ms
• コード長: 16,411 bytes
• コンパイル時間: 2,945 ms
• コンパイル使用メモリ: 210,184 KB
• 実行使用メモリ: 7,848 KB
• 最終ジャッジ日時: 2026-02-28 14:24:59
• 合計ジャッジ時間: 4,203 ms
• ジャッジサーバーID （参考情報）: judge7 / judge4

ファイルパターン	結果
sample	AC * 2
other	AC * 12

ソースコード

fn main() {
    let stdin = std::io::read_to_string(std::io::stdin()).unwrap();
    let mut stdin = stdin.split_ascii_whitespace();

    unsafe {
        read!(stdin -> (k: u16, s: u16, n: u16));
        write!(output(solve(k, s, n)));
    }
}

const fn prepare() -> [u16; 501] {
    const MOD: u16 = 10007;
    let mut f = [1; 501];
    let mut i = 2;
    while i < f.len() {
        f[i] = (f[i - 1] + f[i - 2]) % MOD;
        i += 1;
    }
    i = 2;
    while i < f.len() {
        f[i] = mylib::pow_mod(f[i], MOD - 2, MOD);
        i += 1;
    }
    f
}

fn solve(k: u16, s: u16, n: u16) -> u16 {
    const MOD: u16 = 10007;
    const F_INV: [u16; 501] = prepare();
    let mut dp = [0; 10001];
    dp[1] = s;
    (1..n as usize).for_each(|i| {
        dp[i + 1] = (0..=i.min(k as usize))
            .map(|j| (dp[i - j] as u32 * F_INV[j] as u32 % MOD as u32) as u16)
            .fold(0, |acc, w| (acc + w) % MOD);
    });
    dp[n as usize]
}

fn output(ans: u16) -> String {
    format!("{}", ans)
}

mod mylib {
    pub const fn pow_mod(a: u16, mut b: u16, r#mod: u16) -> u16 {
        let mut ans: u16 = 1;
        let mut mul: u16 = a;
        while b > 0 {
            if (b & 1) == 1 {
                ans = (ans as u32 * mul as u32 % r#mod as u32) as u16;
            }
            mul = (mul as u32 * mul as u32 % r#mod as u32) as u16;
            b >>= 1;
        }
        ans
    }
}

#[macro_export]
macro_rules! read {
    ($iter:ident -> ($v:ident : $t1:tt $([$($t2:tt)+] $({$($t3:tt)+})?)?)) => {
        let $v = read_value!($iter -> $t1 $([$($t2)+] $({$($t3)+})? )?);
    };

    ($iter:ident -> ($v:ident : $t1:tt $([$($t2:tt)+] $({$($t3:tt)+})?)? , $($r:tt)*)) => {
        read!($iter -> ($v : $t1 $([$($t2)+] $({$($t3)+})?)?));
        read!($iter -> ($($r)*));
    };
}

#[macro_export]
macro_rules! read_value {
    ($source:ident -> ($($t1:tt $([$($t2:tt)+])?),+)) => {
        ( $(read_value!($source -> $t1 $([$($t2)+])?)),* )
    };

    ($source:ident -> [ $t1:tt ; $len:expr ]) => {
        {
            let mut x: [::std::mem::MaybeUninit<$t1>; $len] = unsafe { ::std::mem::MaybeUninit::uninit().assume_init() };
            for elem in x.iter_mut() {
                unsafe {
                    elem.as_mut_ptr().write(read_value!($source -> $t1));
                }
            }
            unsafe {
                ::std::mem::transmute::<[::std::mem::MaybeUninit<$t1>; $len], [$t1; $len]>(x)
            }
        }
    };

    ($source:ident -> [ $c2:tt [ $t1:tt $(; $len2:expr)? ] ; $len1:expr ]) => {
        {
            let mut x: [::std::mem::MaybeUninit<$c2<$t1>>; $len1] = unsafe { ::std::mem::MaybeUninit::uninit().assume_init() };
            for elem in x.iter_mut() {
                elem.as_mut_ptr().write(read_value!($source -> $c2 [ $t1 $(; $len2)? ]));
            }
            ::std::mem::transmute::<[::std::mem::MaybeUninit<$c2<$t1>>; $len1], [$c2<$t1>; $len1]>(x)
        }
    };

    ($source:ident -> $t1:tt[ $t2:tt $([$($t3:tt)+])? ; $len:expr ]) => {
        (0..($len)).map(|_| read_value!($source -> $t2 $([$($t3)+])?)).collect::<$t1<_>>()
    };

    ($source:ident -> $t1:tt[ $t2:tt $([$($t3:tt)+])? ]) => {
        (0..(read_value!($source -> u32))).map(|_| read_value!($source -> $t2 $([$($t3)+])?)).collect::<$t1<_>>()
    };

    ($source:ident -> $t1:tt[ ($($t2:tt),+) ; $len:expr ] { $($p1:pat => ($($pos:tt),*)),* }) => {
        (0..($len)).map(|_| {
            let mut v = ($($t2::default()),+);
            v.0 = my_parser::parse_without_checking(($source).next().unwrap());
            match v.0 {
                $($p1 => {
                    $(v.$pos = my_parser::parse_without_checking(($source).next().unwrap()));*
                }),*
                _ => unreachable!(),
            }
            v
        }).collect::<$t1<_>>()
    };

    ($source:ident -> $t1:tt[ ($($t2:tt),+) ] { $($p1:pat => ($($pos:tt),*)),* }) => {
        read_value!($source -> $t1[ $($t2),+ ; read_value!($source -> u32) ] { $($p1 => ($($pos),*)),* })
    };

    ($source:ident -> $t:ty) => {
        my_parser::parse_without_checking::<$t>(($source).next().unwrap())
    };
}

mod my_parser {
    #[allow(unused)]
    pub unsafe fn parse_without_checking<F: std::str::FromStr + Parsable>(target: &str) -> F {
        unsafe { Parsable::from_str(target) }
    }

    pub trait Parsable {
        unsafe fn from_str(s: &str) -> Self;
    }

    impl Parsable for String {
        unsafe fn from_str(s: &str) -> Self {
            Self::from(s)
        }
    }

    impl Parsable for char {
        unsafe fn from_str(s: &str) -> Self {
            s.chars().next().unwrap()
        }
    }

    macro_rules! parse_float {
        ($s:ident) => {{
            let mut iter = $s.bytes().peekable();
            let sign = match iter.peek().unwrap() {
                b'-' => {
                    iter.next();
                    -1.0
                }
                b'+' => {
                    iter.next();
                    1.0
                }
                _ => 1.0,
            };

            let mut result = 0.0;
            while let Some(cur) = iter.next() {
                if cur == b'.' {
                    break;
                }
                result = result * 10.0 + (cur - b'0') as Self;
            }
            let mut digit = 1.0;
            (result
                + iter
                    .map(|cur| {
                        digit *= 0.1;
                        digit * (cur - b'0') as Self
                    })
                    .sum::<Self>())
                * sign
        }};
    }

    impl Parsable for u8 {
        unsafe fn from_str(s: &str) -> Self {
            ((((s.bytes().fold(0, |acc, x| (acc << 8) | (x as u32)) & 0x0f0f0f0f)
                .wrapping_mul((1 << 8) + 10)
                >> 8)
                & 0x00ff00ff)
                .wrapping_mul((1 << 16) + 100)
                >> 16) as Self
        }
    }

    impl Parsable for u16 {
        unsafe fn from_str(s: &str) -> Self {
            ((((((s.bytes().fold(0, |acc, x| (acc << 8) | (x as u64)) & 0x0f0f0f0f0f0f0f0f)
                .wrapping_mul((1 << 8) + 10)
                >> 8)
                & 0x00ff00ff00ff00ff)
                .wrapping_mul((1 << 16) + 100)
                >> 16)
                & 0x0000ffff0000ffff)
                .wrapping_mul((1 << 32) + 10000)
                >> 32) as Self
        }
    }

    impl Parsable for u32 {
        unsafe fn from_str(s: &str) -> Self {
            ((((((((s.bytes().fold(0, |acc, x| (acc << 8) | (x as u128))
                & 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f)
                .wrapping_mul((1 << 8) + 10)
                >> 8)
                & 0x00ff00ff00ff00ff00ff00ff00ff00ff)
                .wrapping_mul((1 << 16) + 100)
                >> 16)
                & 0x0000ffff0000ffff0000ffff0000ffff)
                .wrapping_mul((1 << 32) + 10000)
                >> 32)
                & 0x00000000ffffffff00000000ffffffff)
                .wrapping_mul((1 << 64) + 100000000)
                >> 64) as Self
        }
    }

    impl Parsable for u64 {
        unsafe fn from_str(s: &str) -> Self {
            const POW_10: [u64; 17] = [
                1,
                10,
                100,
                1_000,
                10_000,
                100_000,
                1_000_000,
                10_000_000,
                100_000_000,
                1_000_000_000,
                10_000_000_000,
                100_000_000_000,
                1_000_000_000_000,
                10_000_000_000_000,
                100_000_000_000_000,
                1_000_000_000_000_000,
                10_000_000_000_000_000,
            ];
            s.as_bytes().chunks(16).fold(0, |acc, x| {
                acc * POW_10[x.len()]
                    + ((((((((x.into_iter().fold(0, |acc, &x| (acc << 8) | (x as u128))
                        & 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f)
                        .wrapping_mul((1 << 8) + 10)
                        >> 8)
                        & 0x00ff00ff00ff00ff00ff00ff00ff00ff)
                        .wrapping_mul((1 << 16) + 100)
                        >> 16)
                        & 0x0000ffff0000ffff0000ffff0000ffff)
                        .wrapping_mul((1 << 32) + 10000)
                        >> 32)
                        & 0x00000000ffffffff00000000ffffffff)
                        .wrapping_mul((1 << 64) + 100000000)
                        >> 64) as Self
            })
        }
    }

    impl Parsable for u128 {
        unsafe fn from_str(s: &str) -> Self {
            const POW_10: [u128; 17] = [
                1,
                10,
                100,
                1_000,
                10_000,
                100_000,
                1_000_000,
                10_000_000,
                100_000_000,
                1_000_000_000,
                10_000_000_000,
                100_000_000_000,
                1_000_000_000_000,
                10_000_000_000_000,
                100_000_000_000_000,
                1_000_000_000_000_000,
                10_000_000_000_000_000,
            ];
            s.as_bytes().chunks(16).fold(0, |acc, x| {
                acc * POW_10[x.len()]
                    + ((((((((x.into_iter().fold(0, |acc, &x| (acc << 8) | (x as u128))
                        & 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f)
                        .wrapping_mul((1 << 8) + 10)
                        >> 8)
                        & 0x00ff00ff00ff00ff00ff00ff00ff00ff)
                        .wrapping_mul((1 << 16) + 100)
                        >> 16)
                        & 0x0000ffff0000ffff0000ffff0000ffff)
                        .wrapping_mul((1 << 32) + 10000)
                        >> 32)
                        & 0x00000000ffffffff00000000ffffffff)
                        .wrapping_mul((1 << 64) + 100000000)
                        >> 64) as Self
            })
        }
    }

    impl Parsable for i8 {
        unsafe fn from_str(s: &str) -> Self {
            ((((((s
                .bytes()
                .skip(match s.as_bytes()[0].is_ascii_digit() {
                    true => 0,
                    false => 1,
                })
                .fold(0, |acc, x| (acc << 8) | (x as u32))
                & 0x0f0f0f0f)
                .wrapping_mul((1 << 8) + 10)
                >> 8)
                & 0x00ff00ff)
                .wrapping_mul((1 << 16) + 100)
                >> 16) as i32)
                * match s.as_bytes()[0] == b'-' {
                    true => -1,
                    false => 1,
                }) as Self
        }
    }

    impl Parsable for i16 {
        unsafe fn from_str(s: &str) -> Self {
            ((((((((s
                .bytes()
                .skip(match s.as_bytes()[0].is_ascii_digit() {
                    true => 0,
                    false => 1,
                })
                .fold(0, |acc, x| (acc << 8) | (x as u64))
                & 0x0f0f0f0f0f0f0f0f)
                .wrapping_mul((1 << 8) + 10)
                >> 8)
                & 0x00ff00ff00ff00ff)
                .wrapping_mul((1 << 16) + 100)
                >> 16)
                & 0x0000ffff0000ffff)
                .wrapping_mul((1 << 32) + 10000)
                >> 32) as i64)
                * match s.as_bytes()[0] == b'-' {
                    true => -1,
                    false => 1,
                }) as Self
        }
    }

    impl Parsable for i32 {
        unsafe fn from_str(s: &str) -> Self {
            ((((((((((s
                .bytes()
                .skip(match s.as_bytes()[0].is_ascii_digit() {
                    true => 0,
                    false => 1,
                })
                .fold(0, |acc, x| (acc << 8) | (x as u128))
                & 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f)
                .wrapping_mul((1 << 8) + 10)
                >> 8)
                & 0x00ff00ff00ff00ff00ff00ff00ff00ff)
                .wrapping_mul((1 << 16) + 100)
                >> 16)
                & 0x0000ffff0000ffff0000ffff0000ffff)
                .wrapping_mul((1 << 32) + 10000)
                >> 32)
                & 0x00000000ffffffff00000000ffffffff)
                .wrapping_mul((1 << 64) + 100000000)
                >> 64) as i128)
                * match s.as_bytes()[0] == b'-' {
                    true => -1,
                    false => 1,
                }) as Self
        }
    }

    impl Parsable for i64 {
        unsafe fn from_str(s: &str) -> Self {
            const POW_10: [u64; 17] = [
                1,
                10,
                100,
                1_000,
                10_000,
                100_000,
                1_000_000,
                10_000_000,
                100_000_000,
                1_000_000_000,
                10_000_000_000,
                100_000_000_000,
                1_000_000_000_000,
                10_000_000_000_000,
                100_000_000_000_000,
                1_000_000_000_000_000,
                10_000_000_000_000_000,
            ];
            let skip = match s.as_bytes()[0].is_ascii_digit() {
                true => 0,
                false => 1,
            };
            ((s.as_bytes()[skip..].chunks(16).fold(0, |acc, x| {
                acc * POW_10[x.len()]
                    + ((((((((x.into_iter().fold(0, |acc, &x| (acc << 8) | (x as u128))
                        & 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f)
                        .wrapping_mul((1 << 8) + 10)
                        >> 8)
                        & 0x00ff00ff00ff00ff00ff00ff00ff00ff)
                        .wrapping_mul((1 << 16) + 100)
                        >> 16)
                        & 0x0000ffff0000ffff0000ffff0000ffff)
                        .wrapping_mul((1 << 32) + 10000)
                        >> 32)
                        & 0x00000000ffffffff00000000ffffffff)
                        .wrapping_mul((1 << 64) + 100000000)
                        >> 64) as u64
            }) as i64)
                * match s.as_bytes()[0] == b'-' {
                    true => -1,
                    false => 1,
                }) as Self
        }
    }

    impl Parsable for i128 {
        unsafe fn from_str(s: &str) -> Self {
            const POW_10: [u128; 17] = [
                1,
                10,
                100,
                1_000,
                10_000,
                100_000,
                1_000_000,
                10_000_000,
                100_000_000,
                1_000_000_000,
                10_000_000_000,
                100_000_000_000,
                1_000_000_000_000,
                10_000_000_000_000,
                100_000_000_000_000,
                1_000_000_000_000_000,
                10_000_000_000_000_000,
            ];
            let skip = match s.as_bytes()[0].is_ascii_digit() {
                true => 0,
                false => 1,
            };
            ((s.as_bytes()[skip..].chunks(16).fold(0, |acc, x| {
                acc * POW_10[x.len()]
                    + ((((((((x.into_iter().fold(0, |acc, &x| (acc << 8) | (x as u128))
                        & 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f)
                        .wrapping_mul((1 << 8) + 10)
                        >> 8)
                        & 0x00ff00ff00ff00ff00ff00ff00ff00ff)
                        .wrapping_mul((1 << 16) + 100)
                        >> 16)
                        & 0x0000ffff0000ffff0000ffff0000ffff)
                        .wrapping_mul((1 << 32) + 10000)
                        >> 32)
                        & 0x00000000ffffffff00000000ffffffff)
                        .wrapping_mul((1 << 64) + 100000000)
                        >> 64)
            }) as i128)
                * match s.as_bytes()[0] == b'-' {
                    true => -1,
                    false => 1,
                }) as Self
        }
    }

    impl Parsable for f32 {
        unsafe fn from_str(s: &str) -> Self {
            parse_float!(s)
        }
    }

    impl Parsable for f64 {
        unsafe fn from_str(s: &str) -> Self {
            parse_float!(s)
        }
    }
}

#[macro_export]
macro_rules! write {
    ($out:expr) => {{
        use std::io::Write;
        std::io::stdout()
            .lock()
            .write_all(($out).as_bytes())
            .unwrap();
    }};
}