結果
問題 | No.1552 Simple Dice Game |
ユーザー |
![]() |
提出日時 | 2021-06-22 01:25:05 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 787 ms / 2,500 ms |
コード長 | 5,297 bytes |
コンパイル時間 | 12,213 ms |
コンパイル使用メモリ | 387,996 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-22 23:01:20 |
合計ジャッジ時間 | 22,316 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 20 |
コンパイルメッセージ
warning: unused import: `std::cmp` --> src/main.rs:2:5 | 2 | use std::cmp; | ^^^^^^^^ | = note: `#[warn(unused_imports)]` on by default warning: unused import: `std::cmp::min` --> src/main.rs:3:5 | 3 | use std::cmp::min; | ^^^^^^^^^^^^^ warning: unused import: `std::collections::BTreeMap` --> src/main.rs:4:5 | 4 | use std::collections::BTreeMap; | ^^^^^^^^^^^^^^^^^^^^^^^^^^ warning: unused import: `std::process` --> src/main.rs:5:5 | 5 | use std::process; | ^^^^^^^^^^^^ warning: unused import: `std::collections::HashMap` --> src/main.rs:7:5 | 7 | use std::collections::HashMap; | ^^^^^^^^^^^^^^^^^^^^^^^^^ warning: unused import: `std::collections::HashSet` --> src/main.rs:8:5 | 8 | use std::collections::HashSet; | ^^^^^^^^^^^^^^^^^^^^^^^^^ warning: unused import: `std::collections::BTreeSet` --> src/main.rs:10:5 | 10 | use std::collections::BTreeSet; | ^^^^^^^^^^^^^^^^^^^^^^^^^^ warning: unused import: `std::collections::BinaryHeap` --> src/main.rs:12:5 | 12 | use std::collections::BinaryHeap; | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ warning: unused imports: `Hash`, `Hasher` --> src/main.rs:13:17 | 13 | use std::hash::{Hash, Hasher}; | ^^^^ ^^^^^^ warning: unnecessary parentheses around `while` condition --> src/main.rs:140:10 | 140 | while(b>0){ | ^ ^ | = note: `#[warn(unused_parens)]` on by default help: remove these parentheses | 140 - while(b>0){ 140 + while b>0 { | warning: unnecessary parentheses around `while` condition --> src/main.rs:156:14 | 156 | while(n != 0){ | ^ ^ | help: remove these parentheses | 156 - while(n != 0){ 156 + while n != 0 { | warning: unnecessary parentheses around `if` condition --> src/main.rs:157:16 | 157 | if (n&1 == 1){ans = ans*x%MODu;} | ^ ^ | help: remove these p
ソースコード
use std::cmp::Ordering;use std::cmp;use std::cmp::min;use std::collections::BTreeMap;use std::process;use std::cmp::Ord;use std::collections::HashMap;use std::collections::HashSet;use std::collections::VecDeque;use std::collections::BTreeSet;use std::mem;use std::collections::BinaryHeap;use std::hash::{Hash, Hasher};pub struct Scanner<R> {stdin: R,}impl<R: std::io::Read> Scanner<R> {pub fn read<T: std::str::FromStr>(&mut self) -> T {use std::io::Read;let buf = self.stdin.by_ref().bytes().map(|b| b.unwrap()).skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r').take_while(|&b| b != b' ' && b != b'\n' && b != b'\r').collect::<Vec<_>>();std::str::from_utf8(&buf).unwrap().parse().ok().expect("Parse error.")}pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {(0..n).map(|_| self.read()).collect()}pub fn chars(&mut self) -> Vec<char> {self.read::<String>().chars().collect()}}pub trait BinarySearch<T> {fn lower_bound(&self, x:&T) -> usize;fn upper_bound(&self, x:&T) -> usize;}impl<T: Ord> BinarySearch<T> for VecDeque<T>{fn lower_bound(&self, x: &T) -> usize {let mut low = 0;let mut high = self.len();while low != high {let mid = (low + high) / 2;match self[mid].cmp(x) {Ordering::Less => {low = mid + 1;}Ordering::Equal | Ordering::Greater => {high = mid;}}}low}fn upper_bound(&self, x: &T) -> usize {let mut low = 0;let mut high = self.len();while low != high {let mid = (low + high) / 2;match self[mid].cmp(x) {Ordering::Less | Ordering::Equal => {low = mid + 1;}Ordering::Greater => {high = mid;}}}low}}impl<T: Ord> BinarySearch<T> for [T]{fn lower_bound(&self, x: &T) -> usize {let mut low = 0;let mut high = self.len();while low != high {let mid = (low + high) / 2;match self[mid].cmp(x) {Ordering::Less => {low = mid + 1;}Ordering::Equal | Ordering::Greater => {high = mid;}}}low}fn upper_bound(&self, x: &T) -> usize {let mut low = 0;let mut high = self.len();while low != high {let mid = (low + high) / 2;match self[mid].cmp(x) {Ordering::Less | Ordering::Equal => {low = mid + 1;}Ordering::Greater => {high = mid;}}}low}}fn comb(a:usize, b:usize, fac:&Vec<usize>, ifac:&Vec<usize>)->usize{let mut a = a;let mut b = b;if a == 0 && b == 0{return 1;}if a<b || a<0{return 0;}let mut tmp = ifac[a-b]*ifac[b]%MODu;return tmp * fac[a]%MODu;}fn nHr(n:usize, r:usize, fac:&Vec<usize>, ifac:&Vec<usize>)->usize{return comb(n+r-1, r, fac, ifac);}fn modinv(a:usize, M:usize)->usize{let mut b = M as i64;let mut u = 1 as i64;let mut v = 0 as i64;let mut a = a as i64;let mut m = M as i64;while(b>0){let mut t = a/b;a -= t*b;mem::swap(&mut a, &mut b);u-=t*v;mem::swap(&mut u, &mut v);}u%=m;if u<0{u+=m;}return u as usize;}fn modpow(x:usize, n:usize) -> usize{let mut ans = 1;let mut n = n as usize;let mut x = x;while(n != 0){if (n&1 == 1){ans = ans*x%MODu;}x = x*x%MODu;n = n>>1;}ans}fn invs(max:usize)->(Vec<usize>, Vec<usize>){let mut fac = vec![0;max+1];let mut ifac = vec![0;max+1];fac[0] = 1;ifac[0] = 1;for i in 0..max{fac[i+1] = fac[i] * (i+1)%MODu;ifac[i+1] = ifac[i] * modpow(i+1, MODu - 2)%MODu;}(fac, ifac)}fn solve(){let sssss = std::io::stdin();let mut sc = Scanner { stdin: sssss.lock() };let mut N:usize = sc.read();let mut M:usize = sc.read();let mut res = 0usize;for d in 2..M+1{let mut or = (modpow(d, N)+MODu-modpow(d-2, N))%MODu;let mut A = (modpow(d, N)+MODu-modpow(d-1, N))%MODu;let mut B = (modpow(d, N)+MODu-modpow(d-1, N))%MODu;res+=(A+B+MODu-or)%MODu*(M-d+1)%MODu*(d-1)%MODu*(N%MODu)%MODu*(M+1)%MODu*modinv(2, MODu)%MODu;res%=MODu;}println!("{}", res);}fn main(){solve();}const PI:f64 = std::f64::consts::PI;pub static MOD:i64 = 1000000007;pub static MODu:usize = 998244353;pub static MODi32:i32 = 1000000007;pub static eps:f64 = 1e-6;const INF: i64 = 1 << 60;const INFu:usize = 1<<56;const INFu128:u128 = 1<<126;