結果
問題 |
No.3040 Aoiスコア
|
ユーザー |
|
提出日時 | 2025-03-14 10:50:42 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 3 ms / 1,000 ms |
コード長 | 5,554 bytes |
コンパイル時間 | 11,440 ms |
コンパイル使用メモリ | 400,352 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-06-20 21:03:27 |
合計ジャッジ時間 | 12,688 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#![allow(dead_code, unused_imports, unused_macros, non_snake_case)] use proconio::{ input, input_interactive, marker::{Bytes, Chars, Usize1}, }; const MOD: i64 = 998_244_353; fn main() { input! { n: usize, m : usize, s: Chars, edges: [(Usize1, Usize1); m], } let ntq = s.iter().filter(|&&c| c == '?').count() as i64; let mut g = UndirectedGraph::<()>::new(n); for (u, v) in edges { g.add_edge(u, v, ()); } let mut ans = 0; let inv26 = modinv(26, MOD); for i in 0..n { if s[i] != '?' && s[i] != 'o' { continue; } let ca = g.edges_from(i).filter(|e| s[e.to] == 'a').count() as i64; let ci = g.edges_from(i).filter(|e| s[e.to] == 'i').count() as i64; let cq = g.edges_from(i).filter(|e| s[e.to] == '?').count() as i64; ans += (ca * ci + ca * cq * inv26 + ci * cq * inv26 + cq * (cq - 1) * inv26 % MOD * inv26) % MOD * modpow(26, ntq, MOD) % MOD * if s[i] == '?' { inv26 } else { 1 } % MOD; } println!("{}", ans % MOD); } pub fn modpow(mut x: i64, mut y: i64, modulo: i64) -> i64 { x %= modulo; if x == 0 { return 0; } let mut ret = 1; let mut cur = x; while y > 0 { if y & 1 > 0 { ret = ret * cur % modulo; } cur = cur * cur % modulo; y >>= 1; } ret } pub fn modinv(mut x: i64, modulo: i64) -> i64 { x = x.rem_euclid(modulo); extgcd(x, modulo).0.rem_euclid(modulo) } // return (x, y, gcd(a, b)) s.t. a * x + b * y = gcd(a, b) pub fn extgcd(a: i64, b: i64) -> (i64, i64, i64) { let mut x1 = 1; let mut y1 = 0; let mut m = a; let mut x2 = 0; let mut y2 = 1; let mut n = b; while m % n != 0 { let q = m / n; x1 -= q * x2; y1 -= q * y2; m -= q * n; std::mem::swap(&mut x1, &mut x2); std::mem::swap(&mut y1, &mut y2); std::mem::swap(&mut m, &mut n); } (x2, y2, n) } // ------------ Graph impl start ------------ use std::ops::{Add, AddAssign, Neg, Sub}; pub trait Cost: Clone + Copy + std::fmt::Display + Eq + Ord + Add<Output = Self> + AddAssign + Sub<Output = Self> + Neg<Output = Self> { const ZERO: Self; const MAX: Self; } #[derive(Copy, Clone)] pub struct Edge<C = Void> { // pub from: usize, pub to: usize, pub cost: C, pub id: usize, } pub struct UndirectedGraph<C>(pub Vec<Vec<Edge<C>>>, pub usize); pub struct DirectedGraph<C> { pub forward: Vec<Vec<Edge<C>>>, pub backward: Vec<Vec<Edge<C>>>, pub count: usize, } pub trait Graph<C> { fn new(size: usize) -> Self; fn size(&self) -> usize; fn add_edge(&mut self, u: usize, v: usize, cost: C); fn edges_from(&self, v: usize) -> std::slice::Iter<Edge<C>>; } impl<C: Clone> Graph<C> for UndirectedGraph<C> { fn new(size: usize) -> Self { Self(vec![Vec::<Edge<C>>::new(); size], 0) } fn size(&self) -> usize { self.0.len() } fn add_edge(&mut self, u: usize, v: usize, cost: C) { self.0[u].push(Edge { to: v, cost: cost.clone(), id: self.1, }); self.0[v].push(Edge { to: u, cost, id: self.1, }); self.1 += 1; } fn edges_from(&self, v: usize) -> std::slice::Iter<Edge<C>> { self.0[v].iter() } } impl<C: Clone> Graph<C> for DirectedGraph<C> { fn new(size: usize) -> Self { Self { forward: vec![Vec::<Edge<C>>::new(); size], backward: vec![Vec::<Edge<C>>::new(); size], count: 0, } } fn size(&self) -> usize { self.forward.len() } fn add_edge(&mut self, u: usize, v: usize, cost: C) { self.forward[u].push(Edge { to: v, cost: cost.clone(), id: self.count, }); self.backward[v].push(Edge { to: u, cost, id: self.count, }); self.count += 1; } fn edges_from(&self, v: usize) -> std::slice::Iter<Edge<C>> { self.forward[v].iter() } } impl<C: Clone> DirectedGraph<C> { pub fn edges_to(&self, u: usize) -> std::slice::Iter<Edge<C>> { self.backward[u].iter() } pub fn reverse(&self) -> Self { Self { forward: self.backward.clone(), backward: self.forward.clone(), count: self.count, } } } macro_rules! impl_cost { ($($T:ident,)*) => { $( impl Cost for $T { const ZERO: Self = 0; const MAX: Self = std::$T::MAX; } )* }; } impl_cost! { i8, i16, i32, i64, i128, isize, } #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] pub struct Void; impl std::fmt::Display for Void { fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { write!(f, "Void") } } impl Add for Void { type Output = Self; fn add(self, _: Self) -> Self { self } } impl AddAssign for Void { fn add_assign(&mut self, _: Self) {} } impl Sub for Void { type Output = Self; fn sub(self, _: Self) -> Self { self } } impl Neg for Void { type Output = Self; fn neg(self) -> Self { self } } impl Cost for Void { const ZERO: Self = Void; const MAX: Self = Void; } // ------------ Graph impl end ------------