結果

問題 No.269 見栄っ張りの募金活動
コンテスト
ユーザー RheoTommy
提出日時 2020-11-16 15:58:48
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 33 ms / 5,000 ms
コード長 7,894 bytes
コンパイル時間 12,038 ms
コンパイル使用メモリ 402,316 KB
実行使用メモリ 18,048 KB
最終ジャッジ日時 2024-07-23 01:33:31
合計ジャッジ時間 13,054 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

use crate::lib::{Scanner, ModInt};
// use itertools::Itertools;
use std::collections::*;
use std::process::exit;

const U_INF: usize = 1 << 60;
const I_INF: isize = 1 << 60;

fn main() {
    let mut sc = Scanner::new();
    let n = sc.next_isize();
    let mut s = sc.next_isize();
    let k = sc.next_isize();
    s -= k * (n - 1) * n / 2;

    if s < 0 {
        println!("0");
        exit(0);
    }

    // s円をn人に分ける
    let mut dp = vec![vec![ModInt::new(0); s as usize + 1]; n as usize + 1];
    dp[0][0] = ModInt::new(1);
    for i in 0..=n as usize {
        for j in 0..=s as usize {
            let mut tmp = ModInt::new(0);
            if i != 0 {
                tmp += dp[i - 1][j];
            }
            if j >= i {
                tmp += dp[i][j - i];
            }
            dp[i][j] = tmp;
        }
    }

    println!("{}", dp[n as usize][s as usize]);
}

pub mod lib {
    pub const MOD: isize = 1000000007;

    // pub const MOD: isize = 998244353;

    /// 常に設定したModを取り続ける正整数型
    #[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq)]
    pub struct ModInt {
        /// 保持する値
        value: isize,
    }

    impl ModInt {
        /// isizeを受け取り、ModIntに変換する
        pub fn new(n: isize) -> Self {
            let mut value = n % MOD;
            if value < 0 {
                value += MOD;
            }
            Self { value }
        }

        /// べき乗計算関数
        /// 二分累乗法を用いるため、計算量はO(log n)
        pub fn pow(self, n: usize) -> Self {
            match n {
                0 => ModInt::new(1),
                1 => self,
                n if n % 2 == 0 => (self * self).pow(n / 2),
                _ => self * self.pow(n - 1),
            }
        }

        /// 逆元を返す
        /// フェルマーの小定理より、べき乗を用いて計算するため、計算量はO(log MOD)
        pub fn inv(self) -> Self {
            self.pow((MOD - 2) as usize)
        }
    }

    impl std::fmt::Display for ModInt {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            write!(f, "{}", self.value)
        }
    }

    impl From<usize> for ModInt {
        fn from(n: usize) -> Self {
            Self::new(n as isize)
        }
    }

    impl From<u64> for ModInt {
        fn from(n: u64) -> Self {
            Self::new(n as isize)
        }
    }

    impl From<u32> for ModInt {
        fn from(n: u32) -> Self {
            Self::new(n as isize)
        }
    }

    impl From<u16> for ModInt {
        fn from(n: u16) -> Self {
            Self::new(n as isize)
        }
    }

    impl From<u8> for ModInt {
        fn from(n: u8) -> Self {
            Self::new(n as isize)
        }
    }

    impl From<isize> for ModInt {
        fn from(n: isize) -> Self {
            Self::new(n)
        }
    }

    impl From<i64> for ModInt {
        fn from(n: i64) -> Self {
            Self::new(n as isize)
        }
    }

    impl From<i32> for ModInt {
        fn from(n: i32) -> Self {
            Self::new(n as isize)
        }
    }

    impl From<i16> for ModInt {
        fn from(n: i16) -> Self {
            Self::new(n as isize)
        }
    }

    impl From<i8> for ModInt {
        fn from(n: i8) -> Self {
            Self::new(n as isize)
        }
    }

    impl std::ops::Add for ModInt {
        type Output = Self;

        fn add(self, rhs: Self) -> Self::Output {
            let mut tmp = self.value + rhs.value;
            if tmp >= MOD {
                tmp %= MOD;
            }

            Self { value: tmp }
        }
    }

    impl std::ops::AddAssign for ModInt {
        fn add_assign(&mut self, rhs: Self) {
            *self = *self + rhs
        }
    }

    impl std::ops::Sub for ModInt {
        type Output = ModInt;

        fn sub(self, rhs: Self) -> Self::Output {
            let mut tmp = self.value;
            if tmp < rhs.value {
                tmp += MOD;
            }
            tmp -= rhs.value;
            if tmp >= MOD {
                tmp %= MOD;
            }

            Self { value: tmp }
        }
    }

    impl std::ops::SubAssign for ModInt {
        fn sub_assign(&mut self, rhs: Self) {
            *self = *self - rhs;
        }
    }

    impl std::ops::Mul for ModInt {
        type Output = ModInt;

        fn mul(self, rhs: Self) -> Self::Output {
            let mut tmp = self.value * rhs.value;
            if tmp >= MOD {
                tmp %= MOD;
            }

            Self { value: tmp }
        }
    }

    impl std::ops::MulAssign for ModInt {
        fn mul_assign(&mut self, rhs: Self) {
            *self = *self * rhs;
        }
    }

    impl std::ops::Div for ModInt {
        type Output = ModInt;

        fn div(self, rhs: Self) -> Self::Output {
            self * rhs.inv()
        }
    }

    impl std::ops::DivAssign for ModInt {
        fn div_assign(&mut self, rhs: Self) {
            *self = *self / rhs;
        }
    }

    /// 二項係数を高速に計算するテーブルを作成する
    /// 構築 O(N)
    /// クエリ O(1)
    /// メモリ O(N)
    pub struct CombTable {
        fac: Vec<ModInt>,
        f_inv: Vec<ModInt>,
    }

    impl CombTable {
        /// O(N)で構築
        pub fn new(n: usize) -> Self {
            let mut fac = vec![ModInt::new(1); n + 1];
            let mut f_inv = vec![ModInt::new(1); n + 1];
            let mut inv = vec![ModInt::new(1); n + 1];
            inv[0] = ModInt::new(0);
            for i in 2..=n {
                fac[i] = fac[i - 1] * i.into();
                inv[i] =
                    ModInt::new(MOD) - inv[(MOD % i as isize) as usize] * ModInt::new(MOD / i as isize);
                f_inv[i] = f_inv[i - 1] * inv[i];
            }
            Self { fac, f_inv }
        }

        /// nCkをO(1)で計算
        pub fn comb(&self, n: usize, k: usize) -> ModInt {
            if n < k || n * k == 0 {
                return ModInt::new(0);
            }
            self.fac[n] * (self.f_inv[k] * self.f_inv[n - k])
        }
    }

    pub struct Scanner {
        buf: std::collections::VecDeque<String>,
    }

    impl Scanner {
        pub fn new() -> Self {
            Self {
                buf: std::collections::VecDeque::new(),
            }
        }

        fn scan_line(&mut self) {
            let mut flag = 0;
            while self.buf.is_empty() {
                let mut s = String::new();
                std::io::stdin().read_line(&mut s).unwrap();
                let mut iter = s.split_whitespace().peekable();
                if iter.peek().is_none() {
                    if flag >= 5 {
                        panic!("There is no input!");
                    }
                    flag += 1;
                    continue;
                }

                for si in iter {
                    self.buf.push_back(si.to_string());
                }
            }
        }

        pub fn next<T: std::str::FromStr>(&mut self) -> T {
            self.scan_line();
            self.buf
                .pop_front()
                .unwrap()
                .parse()
                .unwrap_or_else(|_| panic!("Couldn't parse!"))
        }

        pub fn next_usize(&mut self) -> usize {
            self.next()
        }

        pub fn next_isize(&mut self) -> isize {
            self.next()
        }

        pub fn next_chars(&mut self) -> Vec<char> {
            self.next::<String>().chars().collect()
        }

        pub fn next_string(&mut self) -> String {
            self.next()
        }

        pub fn next_char(&mut self) -> char {
            self.next()
        }

        pub fn next_float(&mut self) -> f64 {
            self.next()
        }
    }
}
0