結果
問題 |
No.3117 Reversible Tile
|
ユーザー |
|
提出日時 | 2025-04-16 02:13:34 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 254 ms / 3,000 ms |
コード長 | 975 bytes |
コンパイル時間 | 3,311 ms |
コンパイル使用メモリ | 277,512 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-04-16 02:13:43 |
合計ジャッジ時間 | 7,909 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll=long long; #define rep(i, a, b) for(int i = a; i < (b); i++) const ll mod = 998244353; int main() { int n, m; cin >> n >> m; vector<ll> a(n); rep(i, 0, n) cin >> a[i]; int diff = a[0] + a[n-1]; rep(i, 1, n) if (a[i] != a[i-1]) diff++; vector<ll> dp(n+2); dp[diff] = 1; rep(i, 0, m) { vector<ll> ndp(n+2); rep(j, 0, n+2) { // 境目を二つ選ぶ方法は j * (j - 1) / 2 if (j - 2 >= 0) ndp[j-2] += dp[j] * ((j * (j - 1) / 2) % mod) % mod; // 境目を一つ選ぶ方法は j * (n + 1 - j) ndp[j] += dp[j] * ((j * (n + 1 - j)) % mod) % mod; // 境目を選ばない方法は (n + 1 - j) * (n - j) / 2 if (j + 2 <= n + 1) ndp[j+2] += dp[j] * (((n + 1 - j) * (n - j) / 2) % mod) % mod; } rep(j, 0, n+2) ndp[j] %= mod; dp.swap(ndp); } cout << dp[0] << endl; }