結果
問題 | No.1554 array_and_me |
ユーザー |
![]() |
提出日時 | 2021-06-24 03:34:48 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 59 ms / 2,000 ms |
コード長 | 6,575 bytes |
コンパイル時間 | 12,956 ms |
コンパイル使用メモリ | 378,844 KB |
実行使用メモリ | 5,888 KB |
最終ジャッジ日時 | 2024-06-25 03:44:39 |
合計ジャッジ時間 | 16,054 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
コンパイルメッセージ
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 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 parentheses | 157 - if (n&1 == 1){ans = ans*x%MODu;} 157 + if n&1 == 1 {ans = ans*x%MODu;} | warning: type `x` should have an upp
ソースコード
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)}#[derive(Copy, Clone, Eq, PartialEq)]struct x{a:i64,b:i64,c:i64,d:i64,}impl Ord for x{fn cmp(&self, other:&Self)->Ordering{(other.b * (self.a)).cmp(&((self.b)*other.a))}}impl PartialOrd for x {fn partial_cmp(&self, other: &Self) -> Option<Ordering> {Some(self.cmp(other))}}fn gcd(a:usize, b:usize)->usize{if b==0{return a;}return gcd(b, a%b);}fn solve(){let sssss = std::io::stdin();let mut sc = Scanner { stdin: sssss.lock() };let mut test:usize = sc.read();for _ in 0..test{let mut N:usize = sc.read();let mut K:usize = sc.read();let mut A = vec![0i64;N];let mut s = 0;for i in 0..N{A[i] = sc.read();s+=A[i];}let mut bh = BinaryHeap::new();for i in 0..N{bh.push(x{a:A[i], b:1, c:1, d:A[i]});}let mut res = 1;for i in 0..K{let mut t = bh.pop().unwrap();let mut a = t.a;let mut b = t.b;let mut c = t.c;let mut d = t.d;//println!("i={} K={} {} {} {} {}",i,K, a, b, c, d);let mut tmp = (d*modinv(c as usize, MOD as usize) as i64)%MOD;res *= tmp;res%=MOD;c+=1;let mut g = gcd(c as usize, d as usize) as i64;bh.push(x{a:(d/g), b:(c/g), c:c, d:d});res*=modinv(s as usize, MOD as usize) as i64;res%=MOD;}for i in 1..K as i64 + 1{res*=i;res%=MOD;}println!("{}", res);}}fn main(){solve();}const PI:f64 = std::f64::consts::PI;pub static MOD:i64 = 998244353;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;