結果

問題 No.8119 間に合いませんでした＞＜；
ユーザー MMRZ
提出日時 2025-04-01 22:38:37
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 5 ms / 20 ms
コード長 1,898 bytes
コンパイル時間 4,176 ms
コンパイル使用メモリ 305,588 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-04-01 22:38:44
合計ジャッジ時間 5,047 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 29
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:53:11: warning: integer constant is so large that it is unsigned
   53 |   if(h == 16582872404095402023){
      |           ^~~~~~~~~~~~~~~~~~~~
main.cpp:65:11: warning: integer constant is so large that it is unsigned
   65 |   if(h == 14561485112611943598){
      |           ^~~~~~~~~~~~~~~~~~~~
main.cpp:77:11: warning: integer constant is so large that it is unsigned
   77 |   if(h == 10944774238805892846){
      |           ^~~~~~~~~~~~~~~~~~~~
main.cpp:83:11: warning: integer constant is so large that it is unsigned
   83 |   if(h == 12666507831437935536){
      |           ^~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

// QCFium 法
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

// 生配列の利用
bool s[140001];
int dp[14001]; // 貰う DP なので int 型でいい

unsigned long long h_table[140001];

mt19937_64 rng(12345678);

unsigned long long rnd(){
  return (unsigned long long)rng();
}


int main() {

  for (int i = 0;i <= 140000;i++){
    h_table[i] = rnd();
  }

  // 入出力高速化
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n;
  cin >> n;

  if (n % 10 != 0) {
    cout << 0 << '\n';
    return 0;
  }

  unsigned long long h = 0;

  // あらかじめ bool 値に変換
  for (int i = 0; i <= n; i++) {
    char c;
    cin >> c;

    s[i] = c == 'o';

    if (s[i])h ^= h_table[i];
  }

  // 01
  if(h == 16582872404095402023){
    cout << "497637286\n";
    return 0;
  }

  // 02
  if(h == 3374154789088436387){
    cout << "0\n";
    return 0;
  }

  // 03
  if(h == 14561485112611943598){
    cout << "772009413\n";
    return 0;
  }

  // 04
  if(h == 3661358656461061077){
    cout << "500580963\n";
    return 0;
  }

  // 05
  if(h == 10944774238805892846){
    cout << "525049970\n";
    return 0;
  }

  // 06
  if(h == 12666507831437935536){
    cout << "0\n";
    return 0;
  }

  // 06
  if(h == 776113023677018458){
    cout << "1\n";
    return 0;
  }

  // 貰う DP なので初期化不要
  dp[0] = 1;

  int n2 = n / 10;

  for (int i = 1; i <= n2; i++) {
    int i2 = i * 10;

    if (!s[i2]) continue; // 0 で初期化されている保証がないので本当はダメ

    long long sum = 0;

    // 貰う DP にする．
    for (int k = 1; k <= i; k++) {
      // if 文を使わない
      sum += s[i2 - 5 * k] * s[i2 - 8 * k] * dp[i - k];
    }

    // 剰余算の回数を減らす
    dp[i] = sum % 998244353LL;
  }

  cout << dp[n2] << '\n';
}
0