結果

問題 No.2783 4-33 Easy
ユーザー YY-otterYY-otter
提出日時 2024-06-12 00:28:16
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,096 bytes
コンパイル時間 1,187 ms
コンパイル使用メモリ 90,248 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-14 20:49:58
合計ジャッジ時間 3,580 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 AC 7 ms
6,944 KB
testcase_08 AC 6 ms
6,944 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 WA -
testcase_16 RE -
testcase_17 WA -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 # 

#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