結果

問題 No.1629 Sorting Integers (SUM of M)
ユーザー akiradeveloper
提出日時 2021-07-30 21:38:54
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 8 ms / 2,000 ms
コード長 10,819 bytes
コンパイル時間 13,758 ms
コンパイル使用メモリ 378,500 KB
実行使用メモリ 6,656 KB
最終ジャッジ日時 2024-09-15 23:21:58
合計ジャッジ時間 14,727 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused variable: `out`
   --> src/main.rs:113:13
    |
113 |     let mut out = BufWriter::new(out.lock());
    |             ^^^ help: if this is intentional, prefix it with an underscore: `_out`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: unused variable: `out`
   --> src/main.rs:115:13
    |
115 |     let mut out = BufWriter::new(out.lock());
    |             ^^^ help: if this is intentional, prefix it with an underscore: `_out`

warning: unused variable: `i`
   --> src/main.rs:143:9
    |
143 |     for i in 0..n {
    |         ^ help: if this is intentional, prefix it with an underscore: `_i`

warning: variable does not need to be mutable
   --> src/main.rs:113:9
    |
113 |     let mut out = BufWriter::new(out.lock());
    |         ----^^^
    |         |
    |         help: remove this `mut`
    |
    = note: `#[warn(unused_mut)]` on by default

warning: variable does not need to be mutable
   --> src/main.rs:115:9
    |
115 |     let mut out = BufWriter::new(out.lock());
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: unused variable: `n`
   --> src/main.rs:223:19
    |
223 |     fn nBk(&self, n: i64, k: i64) -> i64 {
    |                   ^ help: if this is intentional, prefix it with an underscore: `_n`

warning: unused variable: `k`
   --> src/main.rs:223:27
    |
223 |     fn nBk(&self, n: i64, k: i64) -> i64 {
    |                           ^ help: if this is intentional, prefix it with an underscore: `_k`

warning: methods `nCk`, `nPk`, `nHk`, `nSk`, and `nBk` are never used
   --> src/main.rs:188:8
    |
161 | impl ModComb {
    | ------------ methods in this implementation
...
188 |     fn nCk(&self, n: i64, k: i64) -> i64 {
    |        ^^^
...
194 |     fn nPk(&self, n: i64, k: i64) -> i64 {
    |        ^^^
...
201 |     fn nHk(&self, n: i64, k: i64) -> i64 {
    |        ^^^
...
208 |     fn nSk(&self, n: i64, k: i64) -> i64 {
    |        ^^^
...
223 |     fn nBk(&self,

ソースコード

diff #
プレゼンテーションモードにする

#[doc = " https://github.com/akiradeveloper/rust-comp-snippets"]
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::iter::FromIterator;
#[macro_export]
macro_rules ! chmax { ( $ x : expr , $ ( $ v : expr ) ,+ ) => { $ ( $ x = std :: cmp :: max ( $ x ,$ v ) ; ) + } ; }
#[macro_export]
macro_rules ! chmin { ( $ x : expr , $ ( $ v : expr ) ,+ ) => { $ ( $ x = std :: cmp :: min ( $ x ,$ v ) ; ) + } ; }
#[macro_export]
macro_rules ! max { ( $ x : expr ) => ( $ x ) ; ( $ x : expr , $ ( $ xs : expr ) ,+ ) => { std :: cmp :: max ( $ x , max ! ( $ ( $ xs ) ,+ ) ) } ; }
#[macro_export]
macro_rules ! min { ( $ x : expr ) => ( $ x ) ; ( $ x : expr , $ ( $ xs : expr ) ,+ ) => { std :: cmp :: min ( $ x , min ! ( $ ( $ xs ) ,+ ) ) } ; }
#[macro_export]
macro_rules ! dvec { ( $ t : expr ; $ len : expr ) => { vec ! [ $ t ; $ len ] } ; ( $ t : expr ; $ len : expr , $ ( $ rest : expr ) ,* ) => { vec ! [ 
    dvec ! ( $ t ; $ ( $ rest ) ,* ) ; $ len ] } ; }
#[macro_export]
macro_rules ! cfor { ( ; $ ( $ rest : tt ) * ) => { cfor ! ( ( ) ; $ ( $ rest ) * ) } ; ( $ ( $ init : stmt ) ,+; ; $ ( $ rest : tt ) * ) => { cfor ! 
    ( $ ( $ init ) ,+; ! false ; $ ( $ rest ) * ) } ; ( $ ( $ init : stmt ) ,+; $ cond : expr ; ; $ body : block ) => { cfor ! { $ ( $ init ) ,+; $ 
    cond ; ( ) ; $ body } } ; ( $ ( $ init : stmt ) ,+; $ cond : expr ; $ ( $ step : expr ) ,+; $ body : block ) => { { $ ( $ init ; ) + while $ cond 
    { let mut _first = true ; let mut _continue = false ; loop { if ! _first { _continue = true ; break } _first = false ; $ body } if ! _continue { 
    break } $ ( $ step ; ) + } } } ; }
#[doc = " main"]
#[allow(unused_imports)]
use std::io::{stdin, stdout, BufWriter, Write};
#[macro_export]
macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut parser = Parser :: from_str ( $ s ) ; input_inner ! { parser , $ ( $ r 
    ) * } } ; ( parser = $ parser : ident , $ ( $ r : tt ) * ) => { input_inner ! { $ parser , $ ( $ r ) * } } ; ( new_stdin_parser = $ parser : 
    ident , $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let reader = std :: io :: BufReader :: new ( stdin . lock ( ) ) ; let mut $ 
    parser = Parser :: new ( reader ) ; input_inner ! { $ parser , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { input ! { new_stdin_parser = parser , 
    $ ( $ r ) * } } ; }
#[macro_export]
macro_rules ! input_inner { ( $ parser : ident ) => { } ; ( $ parser : ident , ) => { } ; ( $ parser : ident , $ var : ident : $ t : tt $ ( $ r : tt 
    ) * ) => { let $ var = read_value ! ( $ parser , $ t ) ; input_inner ! { $ parser $ ( $ r ) * } } ; }
#[macro_export]
macro_rules ! read_value { ( $ parser : ident , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ parser , $ t ) ) ,* ) } ; ( $ parser : ident , [ 
    $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ parser , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ parser : 
    ident , chars ) => { read_value ! ( $ parser , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ parser : ident , usize1 ) => { 
    read_value ! ( $ parser , usize ) - 1 } ; ( $ parser : ident , $ t : ty ) => { $ parser . next ::<$ t > ( ) . expect ( "Parse error" ) } ; }
use std::io;
use std::io::BufRead;
use std::str;
pub struct Parser<R> {
    reader: R,
    buf: Vec<u8>,
    pos: usize,
}
impl Parser<io::Empty> {
    pub fn from_str(s: &str) -> Parser<io::Empty> {
    Parser {
        reader: io::empty(),
        buf: s.as_bytes().to_vec(),
        pos: 0,
    }
    }
}
impl<R: BufRead> Parser<R> {
    pub fn new(reader: R) -> Parser<R> {
    Parser {
        reader: reader,
        buf: vec![],
        pos: 0,
    }
    }
    pub fn update_buf(&mut self) {
    self.buf.clear();
    self.pos = 0;
    loop {
        let (len, complete) = {
        let buf2 = self.reader.fill_buf().unwrap();
        self.buf.extend_from_slice(buf2);
        let len = buf2.len();
        if len == 0 {
            break;
        }
        (len, buf2[len - 1] <= 0x20)
        };
        self.reader.consume(len);
        if complete {
        break;
        }
    }
    }
    pub fn next<T: str::FromStr>(&mut self) -> Result<T, T::Err> {
    loop {
        let mut begin = self.pos;
        while begin < self.buf.len() && (self.buf[begin] <= 0x20) {
        begin += 1;
        }
        let mut end = begin;
        while end < self.buf.len() && (self.buf[end] > 0x20) {
        end += 1;
        }
        if begin != self.buf.len() {
        self.pos = end;
        return str::from_utf8(&self.buf[begin..end]).unwrap().parse::<T>();
        } else {
        self.update_buf();
        }
    }
    }
}
#[allow(unused_macros)]
macro_rules ! debug { ( $ ( $ a : expr ) ,* ) => { eprintln ! ( concat ! ( $ ( stringify ! ( $ a ) , " = {:?}, " ) ,* ) , $ ( $ a ) ,* ) ; } }
#[doc = " https://github.com/hatoo/competitive-rust-snippets"]
const BIG_STACK_SIZE: bool = true;
#[allow(dead_code)]
fn main() {
    use std::thread;
    if BIG_STACK_SIZE {
    thread::Builder::new()
        .stack_size(32 * 1024 * 1024)
        .name("solve".into())
        .spawn(solve)
        .unwrap()
        .join()
        .unwrap();
    } else {
    solve();
    }
}
fn solve() {
    let out = stdout();
    let mut out = BufWriter::new(out.lock());
    let out = stdout();
    let mut out = BufWriter::new(out.lock());
    input!{
        n:usize,
        c:[usize;9],
    }
    let comb = ModComb::new(300000, 1_000_000_007);
    // b[i]があるところに現れる回数
    let mut b: Vec<Mod> = vec![0.into();9];
    for i in 0..9 {
        b[i] = if c[i] > 0 {
            let mut k = comb.fact(n-1).into();
            for j in 0..9 {
                if j == i {
                    k *= comb.fact_inv[c[j]-1];
                } else {
                    // dbg!(c[j]);
                    k *= comb.fact_inv[c[j]];
                }
            }
            k
        } else {
            0.into()
        };
    }
    // dbg!(&b)
    let mut sum: Mod = 0.into();
    let mut x: Mod = 1.into();
    for i in 0..n {
        sum += x;
        x *= 10;
    }
    // dbg!(sum);
    let mut ans: Mod = 0.into();
    for i in 0..9 {
        ans += Mod::from(i as i64 +1) * sum * b[i];
    }
    println!("{}",ans);
}
#[derive(Clone)]
struct ModComb {
    fact: Vec<i64>,
    fact_inv: Vec<i64>,
    n: usize,
    p: i64,
}
impl ModComb {
    fn initialize(ft: &mut Self) {
        let n = ft.n;
        ft.fact[0] = 1;
        for i in 1..n {
            ft.fact[i] = (ft.fact[i - 1] * i as i64) % ft.p;
        }
        ft.fact_inv[n - 1] = modpow(ft.fact[n - 1], ft.p - 2, ft.p);
        for i in (0..n - 1).rev() {
            ft.fact_inv[i] = (ft.fact_inv[i + 1] * (i + 1) as i64) % ft.p;
        }
    }
    #[doc = "O(N)"]
    fn new(max_n: usize, p: i64) -> ModComb {
        let mut ft = ModComb {
            fact: vec![0; max_n + 1],
            fact_inv: vec![0; max_n + 1],
            n: max_n + 1,
            p: p,
        };
        Self::initialize(&mut ft);
        ft
    }
    fn fact(&self, n: usize) -> i64 {
        self.fact[n]
    }
    #[doc = "choose k numbers from 1..n"]
    fn nCk(&self, n: i64, k: i64) -> i64 {
        if n < k {
            return 0;
        }
        (self.nPk(n, k) * self.fact_inv[k as usize]) % self.p
    }
    fn nPk(&self, n: i64, k: i64) -> i64 {
        if n < k {
            return 0;
        }
        self.fact[n as usize] * self.fact_inv[(n - k) as usize] % self.p
    }
    #[doc = "split k into n number as x1+x2+...xn=k"]
    fn nHk(&self, n: i64, k: i64) -> i64 {
        if n == 0 && k == 0 {
            return 1;
        }
        self.nCk(n + k - 1, k)
    }
    #[doc = "put n balls into k different boxes. In case of n=3,k+2 [[1,2],[3]]==[[3],[1,2]]"]
    fn nSk(&self, n: i64, k: i64) -> i64 {
        if n < k {
            return 0;
        }
        let mut res = 0;
        for i in 0..k + 1 {
            let v = self.nCk(k, i) * modpow(i, n, self.p) % self.p;
            if (k - i) % 2 == 1 {
                res = (res + self.p - v) % self.p;
            } else {
                res = (res + v) % self.p;
            }
        }
        return res * self.fact_inv[k as usize] % self.p;
    }
    fn nBk(&self, n: i64, k: i64) -> i64 {
        0
    }
}
#[allow(dead_code)]
#[doc = " x ^ n % m"]
pub fn modpow(x: i64, n: i64, m: i64) -> i64 {
    let mut res = 1;
    let mut x = x % m;
    let mut n = n;
    while n > 0 {
        if n & 1 == 1 {
            res = (res * x) % m;
        }
        x = (x * x) % m;
        n >>= 1;
    }
    res
}
#[doc = " モジュラ逆元"]
#[doc = " "]
#[doc = " ax = 1"]
#[doc = " を満たすxをaの逆元という。"]
#[doc = " "]
#[doc = " aとpが素の場合、"]
#[doc = " フェルマーの小定理より"]
#[doc = " a^(p-1) = 1 (mod p)"]
#[doc = " だから、"]
#[doc = " a a^(p-2) = 1 (mod p)"]
#[doc = " がいえる。"]
#[doc = " これよりa^(p-2)はaの逆元であることがいえる。"]
pub mod modular {
    const M: i64 = 1_000_000_007;
    #[derive(Debug, Clone, Copy, Default, PartialOrd, Ord, PartialEq, Eq)]
    pub struct Mod(pub i64);
    impl ::std::fmt::Display for Mod {
    fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {
        write!(f, "{}", self.0)
    }
    }
    impl Mod {
    pub fn new(v: i64) -> Mod {
        Mod((v + M) % M)
    }
    pub fn pow(self, mut r: i64) -> Mod {
        let mut k = self;
        let mut ret = 1.into();
        while r > 0 {
        if r % 2 != 0 {
            ret = ret * k;
        }
        r /= 2;
        k = k * k;
        }
        ret
    }
    pub fn recip(self) -> Mod {
        self.pow(M - 2)
    }
    }
    use std::ops::*;
    impl<T: Into<Mod>> Add<T> for Mod {
    type Output = Mod;
    fn add(self, rhs: T) -> Self::Output {
        Mod::new(self.0 + rhs.into().0)
    }
    }
    impl<T: Into<Mod>> AddAssign<T> for Mod {
    fn add_assign(&mut self, rhs: T) {
        *self = *self + rhs;
    }
    }
    impl<T: Into<Mod>> Sub<T> for Mod {
    type Output = Mod;
    fn sub(self, rhs: T) -> Self::Output {
        Mod::new(self.0 - rhs.into().0 + M)
    }
    }
    impl<T: Into<Mod>> SubAssign<T> for Mod {
    fn sub_assign(&mut self, rhs: T) {
        *self = *self - rhs;
    }
    }
    impl<T: Into<Mod>> Mul<T> for Mod {
    type Output = Mod;
    fn mul(self, rhs: T) -> Self::Output {
        Mod::new(self.0 * rhs.into().0)
    }
    }
    impl<T: Into<Mod>> MulAssign<T> for Mod {
    fn mul_assign(&mut self, rhs: T) {
        *self = *self * rhs;
    }
    }
    impl<T: Into<Mod>> Div<T> for Mod {
    type Output = Mod;
    fn div(self, rhs: T) -> Self::Output {
        self * rhs.into().recip()
    }
    }
    impl<T: Into<Mod>> DivAssign<T> for Mod {
    fn div_assign(&mut self, rhs: T) {
        *self = *self / rhs;
    }
    }
    impl Neg for Mod {
    type Output = Mod;
    fn neg(self) -> Self::Output {
        Mod(0) - self
    }
    }
    impl<T: ::std::convert::Into<i64>> ::std::convert::From<T> for Mod {
    fn from(v: T) -> Self {
        Mod::new(v.into())
    }
    }
}
pub type Mod = modular::Mod;
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0