結果

問題 No.2783 4-33 Easy
コンテスト
ユーザー YY-otter
提出日時 2024-06-12 00:28:16
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 2,096 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,187 ms
コンパイル使用メモリ 90,248 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-14 20:49:58
合計ジャッジ時間 3,580 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2 RE * 1
other AC * 2 WA * 5 RE * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:8:26: warning: integer overflow in expression of type 'long long int' results in '9223372036854775807' [-Woverflow]
    8 | #define INF_LL ((1LL<<63)-1)
      |                 ~~~~~~~~~^~
main.cpp:79:57: note: in expansion of macro 'INF_LL'
   79 |             ll max_card_num = min(card_a ? a / card_a : INF_LL, min(card_b ? b / card_b : INF_LL, k / 1));
      |                                                         ^~~~~~
main.cpp:8:26: warning: integer overflow in expression of type 'long long int' results in '9223372036854775807' [-Woverflow]
    8 | #define INF_LL ((1LL<<63)-1)
      |                 ~~~~~~~~~^~
main.cpp:79:91: note: in expansion of macro 'INF_LL'
   79 |             ll max_card_num = min(card_a ? a / card_a : INF_LL, min(card_b ? b / card_b : INF_LL, k / 1));
      |                                                                                           ^~~~~~

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>

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

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

int main() {
  ll N;
  cin >> N;

  vector<ll> A(N), B(N);
  for(ll i=0; i<N; i++){
    cin >> A[i];
/*}
  for(ll i=0; i<N; i++){*/
    str temp;
    cin >> temp;

    if(temp == "X")
      B[i] = -1;
    else if(temp.back() == 'X')
      B[i] = -2;
    else
      B[i] = stoll(temp);
  }

  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 i=0; i<N; i++){
    if(B[i] == -1)
      X_freq_table[A[i]]++;
    else if(B[i] >= 0)
      nonX_freq_table[A[i]][B[i]]++;
  }

  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