結果
問題 | No.2964 Obstruction Bingo |
ユーザー |
![]() |
提出日時 | 2024-11-16 15:48:55 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 315 ms / 2,468 ms |
コード長 | 1,122 bytes |
コンパイル時間 | 4,283 ms |
コンパイル使用メモリ | 256,948 KB |
最終ジャッジ日時 | 2025-02-25 04:27:19 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 1000000000000000000LL int main(){ int L,K; cin>>L>>K; string S,T; cin>>S>>T; vector<int> a(26); mint sum = 0; rep(i,26){ cin>>a[i]; sum += a[i]; } vector<mint> p(26); rep(i,26){ p[i] = a[i]; p[i] /= sum; } vector dp(1,vector<mint>(1,1)); mint x = 0,y = 0; rep(i,K){ vector ndp(i+2,vector<mint>(i+2)); rep(j,i+1){ rep(k,i+1){ if(dp[j][k]==0)continue; int cx = S[j%L] - 'a'; int cy = T[k%L] - 'a'; if(cx==cy){ ndp[j+1][k+1] += dp[j][k] * p[cx]; ndp[j][k] += dp[j][k] * (1-p[cx]); } else{ ndp[j+1][k] += dp[j][k] * p[cx]; ndp[j][k+1] += dp[j][k] * p[cy]; ndp[j][k] += dp[j][k] * (1-p[cx]-p[cy]); } } } swap(dp,ndp); rep(j,i+2){ rep(k,i+2){ if(abs(j-k)==L){ if(j<k)y += dp[j][k]; else x += dp[j][k]; dp[j][k] = 0; } } } } cout<<x.val()<<' '<<y.val()<<endl; return 0; }