結果
問題 | No.2058 Binary String |
ユーザー |
![]() |
提出日時 | 2022-08-26 22:37:13 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 310 ms / 2,000 ms |
コード長 | 2,854 bytes |
コンパイル時間 | 11,593 ms |
コンパイル使用メモリ | 387,688 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-13 23:15:37 |
合計ジャッジ時間 | 16,115 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
コンパイルメッセージ
warning: variable does not need to be mutable --> src/main.rs:7:13 | 7 | let mut s = { | ----^ | | | help: remove this `mut` ... 84 | / input! { 85 | | n: i64, 86 | | k: i64, 87 | | }; | |_____- in this macro invocation | = note: `#[warn(unused_mut)]` on by default = note: this warning originates in the macro `input` (in Nightly builds, run with -Z macro-backtrace for more info) warning: variable does not need to be mutable --> src/main.rs:106:9 | 106 | let mut finv: Vec<_> = fact.iter().map(|x| modinv(*x, m)).collect(); | ----^^^^ | | | help: remove this `mut`
ソースコード
macro_rules! input {(source = $s:expr, $($r:tt)*) => {let mut iter = $s.split_whitespace();input_inner!{iter, $($r)*}};($($r:tt)*) => {let mut s = {use std::io::Read;let mut s = String::new();std::io::stdin().read_to_string(&mut s).unwrap();s};let mut iter = s.split_whitespace();input_inner!{iter, $($r)*}};}macro_rules! input_inner {($iter:expr) => {};($iter:expr, ) => {};($iter:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($iter, $t);input_inner!{$iter $($r)*}};}macro_rules! read_value {($iter:expr, ( $($t:tt),* )) => {( $(read_value!($iter, $t)),* )};($iter:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()};($iter:expr, chars) => {read_value!($iter, String).chars().collect::<Vec<char>>()};($iter:expr, usize1) => {read_value!($iter, usize) - 1};($iter:expr, $t:ty) => {$iter.next().unwrap().parse::<$t>().expect("Parse error")};}fn search(x: i64) -> i64 {if x == 0 {return 0;}for i in 0..100 {if (x & (1 << i)) != 0 {return 1+ search(x ^ (1 << i) ^ (1 << (i + 1)));}}panic!();}fn modpow(x: i64, p: i64, m: i64) -> i64 {if p == 0 {1} else if p == 1 {x} else if p % 2 == 1 {x * modpow(x, p - 1, m) % m} else {let t = modpow(x, p / 2, m);t * t % m}}fn modinv(x: i64, m: i64) -> i64{modpow(x, m - 2, m)}fn main() {let m = 998244353;input! {n: i64,k: i64,};if false {let mut cnt = vec![0; 10];for b in 0..(1 << n) {let x: i64 = b;if x.count_ones() % 2 == 0 {let r = search(x);println!("{:b} {} {}", x, x.count_ones(), r);cnt[r as usize] += 1;}}//dbg!(&cnt);}let mut fact = vec![1; (n + 1) as usize];for i in 1.. (n + 1) {fact[i as usize] = fact[(i - 1) as usize] * (i as i64) % m;}let mut finv: Vec<_> = fact.iter().map(|x| modinv(*x, m)).collect();// dbg!(&fact);// dbg!(&finv);//// for i in 0 ..(n + 1) {// fact[i as usize] = modpow(fact[i as usize], k, m);// finv[i as usize] = modpow(finv[i as usize], k, m);// dbg!(&fact[i as usize] * finv[i as usize] % m);// }let mut s = 0;for i in 0..n {let t = fact[(n - 1) as usize] % m * finv[i as usize] % m * finv[(n - i - 1) as usize] % m;//dbg!(&t);s += modpow(i, k, m) * t;s %= m;}println!("{}", s);}