結果
| 問題 | No.3809 Count Bipartite Permutations |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-20 23:36:27 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 190 ms / 2,000 ms |
| + 48µs | |
| コード長 | 847 bytes |
| 記録 | |
| コンパイル時間 | 4,698 ms |
| コンパイル使用メモリ | 382,120 KB |
| 実行使用メモリ | 9,872 KB |
| 最終ジャッジ日時 | 2026-11-20 23:37:05 |
| 合計ジャッジ時間 | 9,205 ms |
|
ジャッジサーバーID (参考情報) |
judge1_0 / judge5_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 30 |
ソースコード
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using ll = long long;
using mint = atcoder::modint998244353;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
constexpr int th = 6400;
if(k > th){
cout << "0\n";
return 0;
}
vector<array<mint,th + 1>> dp(n + 1);
dp[0][0] = 1;
for(int i = 1; i <= 2 * n; i++){
vector<array<mint,th + 1>> ndp(n + 1);
for(int j = 0; j <= n; j++){
for(int k = 0; k <= th; k++){
if(j + 1 <= n && i + k <= th) ndp[j + 1][i + k] += dp[j][k];
if(j >= 1) ndp[j - 1][k] += dp[j][k] * mint::raw(j);
}
}
swap(dp, ndp);
}
mint ans = dp[0][k];
for(int i = 1; i <= n; i++) ans *= mint::raw(i);
cout << ans.val() << '\n';
}