結果
問題 |
No.3040 Aoiスコア
|
ユーザー |
|
提出日時 | 2025-02-28 22:08:37 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 141 ms / 1,000 ms |
コード長 | 3,504 bytes |
コンパイル時間 | 15,151 ms |
コンパイル使用メモリ | 396,300 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-06-20 20:58:18 |
合計ジャッジ時間 | 12,423 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#[allow(unused_imports)] use std::{ cell::RefCell, convert::{Infallible, TryFrom, TryInto as _}, fmt::{self, Debug, Display, Formatter,}, fs::{File}, hash::{Hash, Hasher}, iter::{Product, Sum}, marker::PhantomData, ops::{Add, AddAssign, Sub, SubAssign, Div, DivAssign, Mul, MulAssign, Neg, }, str::FromStr, sync::{atomic::{self, AtomicU32, AtomicU64}, Once}, collections::{*}, mem::{swap}, cmp::{self, Reverse, Ordering, Eq, PartialEq, PartialOrd}, thread::LocalKey, f64::consts::PI, time::Instant, io::{self, stdin, Read, read_to_string, BufWriter, BufReader, stdout, Write}, }; #[allow(unused_imports)] use proconio::{input, input_interactive, marker::{*}}; #[allow(unused_imports)] //use rand::{thread_rng, Rng, seq::SliceRandom}; #[allow(unused_imports)] //use ac_library::{*}; #[allow(dead_code)] const INF: i64 = 1<<60; #[allow(dead_code)] const MOD: i64 = 998244353; #[allow(dead_code)] const D: [(usize, usize); 4] = [(1, 0), (0, 1), (!0, 0), (0, !0)]; pub fn floor(a:i64, b:i64)->i64{let res=(a%b+b)%b;(a-res)/b} pub fn extended_gcd(a:i64,b:i64)->(i64,i64,i64) {if b==0{(a,1,0)}else{let(g,x,y)=extended_gcd(b,a%b);(g,y,x-floor(a,b)*y)}} pub fn mod_inverse(a:i64,m:i64)->i64{let(_,x,_) =extended_gcd(a,m);(x%m+m)%m} pub fn comb(a: i64, b: i64, f: &Vec<(i64, i64)>)->i64{ if a<b{return 0;}if b==0 || a==b{ return 1; } else{let x=f[a as usize].0; let y=f[(a-b) as usize].1;let z=f[b as usize].1;return((x*y)%MOD)*z%MOD;}} pub fn factorial(x: i64)->Vec<(i64, i64)>{ let mut f=vec![(1i64,1i64),(1, 1)];let mut z = 1i64; let mut inv = vec![0; x as usize+10];inv[1] = 1; for i in 2..x+1{z=(z*i)%MOD; let w=(MOD-inv[(MOD%i)as usize]*(MOD/i)%MOD)%MOD; inv[i as usize] = w; f.push((z, (f[i as usize-1].1*w)%MOD));}return f;} pub fn fast_mod_pow(x: i64,p: usize, m: i64)->i64{ let mut res=1;let mut t=x;let mut z=p;while z > 0{ if z%2==1{res = (res*t)%m;}t = (t*t)%m;z /= 2; }res} //use proconio::fastout; //#[fastout] fn main(){ input!{ n: usize, m: usize, s: Chars, e: [(Usize1, Usize1); m], } let mut cnt = 0; for &c in &s{ if c=='?'{ cnt += 1; } } let mut num = vec![fast_mod_pow(26, cnt, MOD)]; if cnt >= 1{ num.push(fast_mod_pow(26, cnt-1, MOD)); } if cnt >= 2{ num.push(fast_mod_pow(26, cnt-2, MOD)); } if cnt >= 3{ num.push(fast_mod_pow(26, cnt-3, MOD)); } let mut edge = vec![Vec::new(); n]; for &(u, v) in &e{ edge[u].push(v); edge[v].push(u); } let mut ans = 0; for i in 0..n{ if s[i]=='?'{ dfs(i, !0, 1, &num, &edge, &s, &mut ans); } else if s[i]=='a'{ dfs(i, !0, 0, &num, &edge, &s, &mut ans); } } println!("{}", ans); } fn dfs(p: usize, pre: usize, cnt: usize, num: &Vec<i64>, edge: &Vec<Vec<usize>>, s: &Vec<char>, ans: &mut i64){ if pre > edge.len(){ for &nex in &edge[p]{ if s[nex]=='?'{ dfs(nex, p, cnt+1, num, edge, s, ans); } else if s[nex]=='o'{ dfs(nex, p, cnt, num, edge, s, ans); } } } else { for &nex in &edge[p]{ if nex==pre{continue} if s[nex]=='?'{ *ans = (*ans+num[cnt+1])%MOD; } else if s[nex]=='i'{ *ans = (*ans+num[cnt])%MOD; } } } }