結果

問題 No.2788 4-33 Hard
コンテスト
ユーザー YY-otter
提出日時 2024-06-13 09:27:32
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 7 ms / 2,000 ms
コード長 2,112 bytes
コンパイル時間 408 ms
コンパイル使用メモリ 32,384 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-14 20:49:59
合計ジャッジ時間 2,137 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 52
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'main':
main.c:75:13: warning: integer overflow in expression '-9223372036854775808 - 1' of type 'long long int' results in '9223372036854775807' [-Woverflow]
   75 |             ll max_card_num = min(card_a ? a / card_a : INF_LL, min(card_b ? b / card_b : INF_LL, k / 1));
      |             ^~
main.c:75:13: warning: integer overflow in expression '-9223372036854775808 - 1' of type 'long long int' results in '9223372036854775807' [-Woverflow]

ソースコード

diff # 

#include <stdio.h>

typedef long long int ll;

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

ll min(ll a, ll b) {ll ans = a > b ? b : a; return ans;}

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

  ll nonX_freq_table[5][34] = {{}};
  ll X_freq_table[5] = {};

  for(ll a=0; a<MAX_A; a++){
    for(ll b=0; b<MAX_B; b++){
      scanf("%lld", &nonX_freq_table[a][b]);
    }
  }
  for(ll a=0; a<MAX_A; a++){
    for(ll b=0; b<MAX_B; b++){
      if(b==0)
        scanf("%lld", &X_freq_table[a]);
      else{
        ll ignored;
        scanf("%lld", &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[9][5][34] = {{{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;
  }

  printf("%lld\n", ans);
  return 0;
}
0