結果

問題 No.3371 Add Insert Operations
コンテスト
ユーザー rhoo
提出日時 2025-10-25 12:34:40
言語 Rust
(1.83.0 + proconio)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 905 bytes
コンパイル時間 14,014 ms
コンパイル使用メモリ 403,904 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-11-17 20:30:23
合計ジャッジ時間 14,469 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 WA * 14 RE * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

use proconio::{marker::*,*};


fn main(){
    input!{
        s:Chars,
    }
    
    let n=s.len();
    let s=s.iter().map(|&c|(c as u8-'A' as u8+1) as usize).collect::<Vec<_>>();
    
    if (1..n).all(|i|s[i-1]==s[i]){
        println!("1");
        return;
    }
    
    const MOD:u64=998244353;

    let mut sum=vec![0;n+1];
    let mut next=vec![[!0;4];n+1];
    next[n][0]=n;

    for i in (0..n).rev(){
        sum[i]=sum[i+1]^s[i];
        for j in 0..4{
            next[i][j]=next[i+1][j];
        }
        next[i][sum[i]]=i;
    }

    let mut dp=vec![0;n+1];
    dp[0]=1;
    let mut ans=0;

    for i in 0..=n{
        if sum[i]==0{
            ans=(ans+dp[i])%MOD;
        }
        for &ni in &next[i]{
            if ni!=i && ni!=!0{
                dp[ni]=(dp[ni]+dp[i])%MOD;
            }
        }
    }

    if sum[0]==0{
        ans=(ans+MOD-1)%MOD;
    }

    println!("{ans}");
}
0