結果

問題 No.2149 Vanitas Vanitatum
コンテスト
ユーザー miie
提出日時 2024-11-04 19:32:10
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 151 ms / 2,000 ms
コード長 1,456 bytes
コンパイル時間 3,441 ms
コンパイル使用メモリ 255,852 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-04 19:32:15
合計ジャッジ時間 5,123 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/modint>
using namespace std;
using mint = atcoder::modint998244353;

// A : A[i] >= A[i+1]
mint solve(vector<int> A){
  int H = A.size();
  if(H == 0) return 1;
  int sum = 0;
  for(int i=0; i<H; i++){
    sum += A[i];
  }
  mint ret = 1;
  for(int i=1; i<=sum; i++){
    ret *= i;
  }
  vector<int> cnt(A[0]+1, 0);
  for(int i=H-1; i>=0; i--){
    for(int j=1; j<=A[i]; j++){
      cnt[j]++;
      int w = A[i]-j+1;
      int h = cnt[j];
      ret /= w+h-1;
    }
  }
  return ret;
}

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  int sum = 0;
  for(int i=0; i<n; i++){
    cin >> a[i];
    sum += a[i];
  }
  if(sum%2 == 1){
    cout << 0 << endl;
    return 0;
  }
  string s = string(a[0], '1') + "0";
  for(int i=1; i<n; i++){
    s += string(a[i]-a[i-1], '1') + "0";
  }
  vector<int> A(1, 0), B(1, 0);
  for(int i=0; i<(int)s.size(); i++){
    if(s[i] == '1'){
      A.back()++;
    }
    else{
      A.push_back(A.back());
    }
    swap(A, B);
  }
  A.pop_back();
  B.pop_back();
  reverse(A.begin(), A.end());
  reverse(B.begin(), B.end());
  int suma = 0, sumb = 0;
  for(int x : A){
    suma += x;
  }
  for(int y : B){
    sumb += y;
  }
  if((suma + sumb)*2 != sum){
    cout << 0 << endl;
    return 0;
  }
  mint ans = solve(A)*solve(B);
  for(int i=1; i<=suma+sumb; i++) ans *= i;
  for(int i=1; i<=suma; i++) ans /= i;
  for(int i=1; i<=sumb; i++) ans /= i;
  cout << ans.val() << endl;
}
0