結果
| 問題 | No.2356 Back Door Tour in Four Seasons |
| ユーザー |
 naut3
|
| 提出日時 | 2023-06-18 13:44:58 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 1,338 ms / 2,000 ms |
| コード長 | 5,855 bytes |
| コンパイル時間 | 14,415 ms |
| コンパイル使用メモリ | 393,140 KB |
| 実行使用メモリ | 44,716 KB |
| 最終ジャッジ日時 | 2024-06-26 02:46:06 |
| 合計ジャッジ時間 | 56,055 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 28 |
コンパイルメッセージ
warning: unused `Result` that must be used
--> src/main.rs:65:5
|
65 | writeln!(out, "{}", ans);
| ^^^^^^^^^^^^^^^^^^^^^^^^
|
= note: this `Result` may be an `Err` variant, which should be handled
= note: `#[warn(unused_must_use)]` on by default
= note: this warning originates in the macro `writeln` (in Nightly builds, run with -Z macro-backtrace for more info)
ソースコード
#![allow(non_snake_case, unused_imports)]use std::io::{self, prelude::*};use std::str;fn main() {let (stdin, stdout) = (io::stdin(), io::stdout());let mut scan = Scanner::new(stdin.lock());let mut out = io::BufWriter::new(stdout.lock());macro_rules! input {($T: ty) => {scan.token::<$T>()};}let N = input!(usize);const MOD: usize = 998_244_353;let M = 100_001;let mut U = vec![0; M];let mut F = vec![0; M];let mut W = vec![0; M];let mut P = vec![0; M];let mut all_door = 0;for _ in 0..N {let S = input!(String);let A = input!(usize);all_door += A;if S == "U" {U[A] += MOD + ntt::pow_mod(N - 1, A) - ntt::pow_mod(N - 2, A);U[A] %= MOD;} else if S == "F" {F[A] += MOD + ntt::pow_mod(N - 1, A) - ntt::pow_mod(N - 2, A);F[A] %= MOD;} else if S == "W" {W[A] += MOD + ntt::pow_mod(N - 1, A) - ntt::pow_mod(N - 2, A);W[A] %= MOD;} else {P[A] += ntt::pow_mod(N - 1, A);P[A] %= MOD;}}let cnt = {let a = ntt::conv(U, F);let b = ntt::conv(a, W);let c = ntt::conv(b, P);c};let mut ans = 0;for (i, &c) in cnt.iter().enumerate() {if c > 0 {let other_pattern = ntt::pow_mod(N - 1, all_door - i);ans += c * other_pattern;ans %= MOD;}}writeln!(out, "{}", ans);}struct Scanner<R> {reader: R,buf_str: Vec<u8>,buf_iter: str::SplitWhitespace<'static>,}impl<R: BufRead> Scanner<R> {fn new(reader: R) -> Self {Self {reader,buf_str: vec![],buf_iter: "".split_whitespace(),}}fn token<T: str::FromStr>(&mut self) -> T {loop {if let Some(token) = self.buf_iter.next() {return token.parse().ok().expect("Failed parse");}self.buf_str.clear();self.reader.read_until(b'\n', &mut self.buf_str).expect("Failed read");self.buf_iter = unsafe {let slice = str::from_utf8_unchecked(&self.buf_str);std::mem::transmute(slice.split_whitespace())}}}}pub mod ntt {const MOD: usize = 998_244_353;const ROOT: [usize; 24] = [1, 998244352, 911660635, 372528824, 929031873, 452798380, 922799308, 781712469, 476477967,166035806, 258648936, 584193783, 63912897, 350007156, 666702199, 968855178, 629671588,24514907, 996173970, 363395222, 565042129, 733596141, 267099868, 15311432,];const ROOT_INV: [usize; 24] = [1, 998244352, 86583718, 509520358, 337190230, 87557064, 609441965, 135236158, 304459705,685443576, 381598368, 335559352, 129292727, 358024708, 814576206, 708402881, 283043518,3707709, 121392023, 704923114, 950391366, 428961804, 382752275, 469870224,];pub fn pow_mod(x: usize, m: usize) -> usize {let mut ret = 1;let mut val = x;for i in 0..60 {if (m >> i) & 1 == 1 {ret *= val;ret %= MOD;}val *= val;val %= MOD;}ret}pub fn inv_mod(x: usize) -> usize {return pow_mod(x, MOD - 2);}pub fn ntt(mut f: Vec<usize>, depth: usize) -> Vec<usize> {let n = f.len();if n == 1 {return f;}let mut even = vec![0; n / 2];let mut odd = vec![0; n / 2];for i in 0..n / 2 {even[i] = f[2 * i];odd[i] = f[2 * i + 1];}even = ntt(even, depth - 1);odd = ntt(odd, depth - 1);let r = ROOT[depth];let mut now = 1;for i in 0..n / 2 {odd[i] *= now;odd[i] %= MOD;f[i] = (even[i] + odd[i]) % MOD;f[i + n / 2] = (MOD + even[i] - odd[i]) % MOD;now *= r;now %= MOD;}return f;}pub fn intt(mut f: Vec<usize>, depth: usize) -> Vec<usize> {let n = f.len();if n == 1 {return f;}let mut even = vec![0; n / 2];let mut odd = vec![0; n / 2];for i in 0..n / 2 {even[i] = f[2 * i];odd[i] = f[2 * i + 1];}even = intt(even, depth - 1);odd = intt(odd, depth - 1);let r = ROOT_INV[depth];let mut now = 1;for i in 0..n / 2 {odd[i] *= now;odd[i] %= MOD;f[i] = (even[i] + odd[i]) % MOD;f[i + n / 2] = (MOD + even[i] - odd[i]) % MOD;now *= r;now %= MOD;}return f;}pub fn conv(mut f: Vec<usize>, mut g: Vec<usize>) -> Vec<usize> {let mut l = 1;let mut d = 0;while f.len() + g.len() - 1 >= l {l <<= 1;d += 1;}while f.len() < l {f.push(0);}while g.len() < l {g.push(0);}assert!(f.len() == g.len());let F = ntt(f, d);let G = ntt(g, d);assert!(F.len() == G.len());let H = {let mut ret = vec![0; l];for i in 0..l {ret[i] = F[i] * G[i];ret[i] %= MOD;}ret};let h = {let mut ret = intt(H, d);let l_inv = inv_mod(l);for i in 0..l {ret[i] *= l_inv;ret[i] %= MOD;}ret};h}}