結果
問題 |
No.2388 At Least K-Characters
|
ユーザー |
👑 |
提出日時 | 2023-07-15 13:23:03 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 43 ms / 4,000 ms |
コード長 | 1,775 bytes |
コンパイル時間 | 18,410 ms |
コンパイル使用メモリ | 391,128 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-05 03:38:38 |
合計ジャッジ時間 | 21,197 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
use std::io::prelude::*; fn main() { let mut input = String::new(); std::io::stdin().read_to_string(&mut input).unwrap(); const MOD: u64 = 998244353; const KMAX: usize = 26; const KMAX2: usize = KMAX + 2; let mut tokens = input.split_ascii_whitespace(); let n = tokens.next().unwrap().parse::<usize>().unwrap(); let m = tokens.next().unwrap().parse::<usize>().unwrap(); let k = tokens.next().unwrap().parse::<usize>().unwrap(); let s = tokens.next().unwrap(); if n < 1 || n != s.len() || n > m || m > 500000 || k < 1 || k > KMAX { panic!(); } let mut kbits = 0u32; let mut kbc = 0usize; let mut dp = [0u64; KMAX2]; let mut result = 0u64; for c in s.bytes() { let mut ndp = [0u64; KMAX2]; let ci = (c - b'a') as usize; if ci >= KMAX { panic!(); } let same = (kbits & ((1 << ci) - 1)).count_ones() as u64; ndp[kbc] += same; ndp[kbc + 1] += (ci as u64) - same; if (kbits & (1 << ci)) == 0 { kbits |= 1 << ci; kbc += 1; } if kbc >= k { result += 1; } for j in 1..=KMAX { ndp[j] += (j as u64) * dp[j]; ndp[j + 1] += ((KMAX - j) as u64) * dp[j]; ndp[j] %= MOD; } for &je in ndp[k..=KMAX].iter() { result += je; } dp = ndp; } if kbc >= k { result -= 1; } for _ in n..m { let mut ndp = [0u64; KMAX2]; for j in 1..=KMAX { ndp[j] += (j as u64) * dp[j]; ndp[j + 1] += ((KMAX - j) as u64) * dp[j]; ndp[j] %= MOD; } for &je in ndp[k..=KMAX].iter() { result += je; } dp = ndp; } result %= MOD; println!("{}", result); }