結果
問題 | No.3117 Reversible Tile |
ユーザー |
|
提出日時 | 2025-04-08 20:44:20 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 259 ms / 3,000 ms |
コード長 | 874 bytes |
コンパイル時間 | 5,805 ms |
コンパイル使用メモリ | 334,024 KB |
実行使用メモリ | 7,848 KB |
最終ジャッジ日時 | 2025-04-08 20:44:31 |
合計ジャッジ時間 | 9,898 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using ll = long long; using namespace atcoder; constexpr ll mod = 998244353; constexpr ll inv = 499122177; int n,m,a[5005],cnt; int main(){ cin >> n >> m; a[0] = 0,a[n + 1] = 0; for(int i=1;i<=n;i++) cin >> a[i]; for(int i = 0; i <= n; i++){ if(a[i] == a[i + 1]) cnt++; } vector<ll> dp(n + 2,0); dp[cnt] = 1; for(int i = 0; i < m; i++){ vector<ll> ndp(n + 2,0); for(int j = 0; j <= n + 1; j++){ if(j >= 2) ndp[j - 2] += (((dp[j] * j * (j - 1)) % mod) * inv) % mod; ndp[j] += (dp[j] * j * (n + 1 - j)) % mod; if(j + 2 <= n + 1) ndp[j + 2] += ((dp[j] * (n + 1 - j) * (n - j)) % mod * inv) % mod; } for(int j = 0; j <= n + 1; j++) ndp[j] %= mod; swap(dp,ndp); } cout << dp[n + 1]; }