結果

問題 No.2788 4-33 Hard
コンテスト
ユーザー YY-otter
提出日時 2024-06-13 09:07:12
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 8 ms / 2,000 ms
コード長 2,085 bytes
コンパイル時間 811 ms
コンパイル使用メモリ 80,276 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-14 20:49:58
合計ジャッジ時間 2,763 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 52
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:7:26: warning: integer overflow in expression of type 'long long int' results in '9223372036854775807' [-Woverflow]
    7 | #define INF_LL ((1LL<<63)-1)
      |                 ~~~~~~~~~^~
main.cpp:75:57: note: in expansion of macro 'INF_LL'
   75 |             ll max_card_num = min(card_a ? a / card_a : INF_LL, min(card_b ? b / card_b : INF_LL, k / 1));
      |                                                         ^~~~~~
main.cpp:7:26: warning: integer overflow in expression of type 'long long int' results in '9223372036854775807' [-Woverflow]
    7 | #define INF_LL ((1LL<<63)-1)
      |                 ~~~~~~~~~^~
main.cpp:75:91: note: in expansion of macro 'INF_LL'
   75 |             ll max_card_num = min(card_a ? a / card_a : INF_LL, min(card_b ? b / card_b : INF_LL, k / 1));
      |                                                                                           ^~~~~~

ソースコード

diff # 

#include <iostream>

using namespace std;
typedef long long ll;
typedef string str;

#define INF_LL ((1LL<<63)-1)
#define MOD 998244353

int main() {
  const ll MAX_K = 9, MAX_A = 5, MAX_B = 34;

  ll nonX_freq_table[MAX_A][MAX_B] = {{}};
  ll X_freq_table[MAX_A] = {};

  for(ll a=0; a<MAX_A; a++){
    for(ll b=0; b<MAX_B; b++){
      cin >> nonX_freq_table[a][b];
    }
  }
  for(ll a=0; a<MAX_A; a++){
    for(ll b=0; b<MAX_B; b++){
      if(b==0)
        cin >> X_freq_table[a];
      else{
        ll ignored;
        cin >> ignored;
      }
    }
  }

  for(ll a=0; a<MAX_A; a++){
    for(ll b=0; b<MAX_B; b++){
      nonX_freq_table[a][b] %= MOD;
    }
    X_freq_table[a] %= MOD;
  }

  ll modinv_table[MAX_K];

  modinv_table[0] = 0;
  for(ll i=1; i<MAX_K; i++){
    ll inv = 1;

    for(ll j=0; j<i; j++){
      if(inv % i == 0){
        modinv_table[i] = inv / i;
        break;
      }
      else
        inv += MOD;
    }
  }

  ll comb_table[MAX_K][MAX_A][MAX_B];
  for(ll k=0; k<MAX_K; k++){
    for(ll a=0; a<MAX_A; a++){
      for(ll b=0; b<MAX_B; b++){
        if(k == 0)
          comb_table[k][a][b] = 1;
        else{
          comb_table[k][a][b] = (((comb_table[k-1][a][b] * (nonX_freq_table[a][b] - k + 1))%MOD) * modinv_table[k])%MOD;
        }
      }
    }
  }

  ll dp_table[MAX_K][MAX_A][MAX_B] = {{{1}}};

  for(ll card_a=0; card_a<MAX_A; card_a++){
    for(ll card_b=0; card_b<MAX_B; card_b++){
      for(ll k=MAX_K-1; k>=0; k--){
        for(ll a=0; a<MAX_A; a++){
          for(ll b=0; b<MAX_B; b++){
            ll max_card_num = min(card_a ? a / card_a : INF_LL, min(card_b ? b / card_b : INF_LL, k / 1));
            for(ll card_num = 1; card_num <= max_card_num; card_num++)
              dp_table[k][a][b] = (dp_table[k][a][b] + (dp_table[k-card_num][a-card_num*card_a][b-card_num*card_b] * comb_table[card_num][card_a][card_b])%MOD)%MOD;
          }
        }
      }
    }
  }

  ll ans = 0;

  for(ll i=0; i<MAX_A; i++){
    ans = (ans+(dp_table[MAX_K-1][MAX_A-1-i][MAX_B-1]*X_freq_table[i])%MOD)%MOD;
  }

  cout << ans << endl;
  return 0;
}
0