結果

問題 No.2846 Birthday Cake
ユーザー Andrew8128Andrew8128
提出日時 2024-08-23 23:29:05
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,839 ms / 2,000 ms
コード長 2,510 bytes
コンパイル時間 5,493 ms
コンパイル使用メモリ 311,248 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-08-23 23:29:30
合計ジャッジ時間 25,381 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 889 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 1,177 ms
6,940 KB
testcase_06 AC 1,442 ms
6,940 KB
testcase_07 AC 1,614 ms
6,940 KB
testcase_08 AC 1,750 ms
6,944 KB
testcase_09 AC 1,793 ms
6,940 KB
testcase_10 AC 1,797 ms
6,940 KB
testcase_11 AC 1,839 ms
6,944 KB
testcase_12 AC 447 ms
6,940 KB
testcase_13 AC 672 ms
6,940 KB
testcase_14 AC 6 ms
6,944 KB
testcase_15 AC 14 ms
6,940 KB
testcase_16 AC 36 ms
6,940 KB
testcase_17 AC 705 ms
6,940 KB
testcase_18 AC 1,837 ms
6,944 KB
testcase_19 AC 2 ms
6,940 KB
testcase_20 AC 2 ms
6,940 KB
testcase_21 AC 2 ms
6,940 KB
testcase_22 AC 6 ms
6,944 KB
testcase_23 AC 2 ms
6,940 KB
testcase_24 AC 705 ms
6,940 KB
testcase_25 AC 2 ms
6,940 KB
testcase_26 AC 6 ms
6,944 KB
testcase_27 AC 13 ms
6,940 KB
testcase_28 AC 2 ms
6,944 KB
testcase_29 AC 14 ms
6,940 KB
testcase_30 AC 2 ms
6,940 KB
testcase_31 AC 2 ms
6,944 KB
testcase_32 AC 246 ms
6,944 KB
testcase_33 AC 698 ms
6,944 KB
testcase_34 AC 35 ms
6,944 KB
testcase_35 AC 37 ms
6,940 KB
testcase_36 AC 600 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 441_E.cpp   2024/08/23 21:44:34
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353, mod1 = 1000000007, inf = 1070000000;
const ll linf = 4610000000000000000;
#define REP(i,x,y) for (auto i = (x); i < (y); i++)
#define RREP(i,x,y) for (auto i = (y) - 1; (x) <= i; i--)
#define ALL(x) (x).begin(), (x).end()
template<class T> bool inr(const T &l, const T &x, const T &r){return (l<=x && x<r);}
template<class T> bool chmax(T &a, const T &b){if(a < b){a = b; return 1;} else return 0;}
template<class T> bool chmin(T &a, const T &b){if(b < a){a = b; return 1;} else return 0;}
#include <atcoder/all>
using namespace atcoder;
#pragma GCC optimize("O3")
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  short K,N;
  cin >> K >> N;
  ll ans = 0;
  if(K == 13)ans++;
  if(K == 17)ans++;
  if(K == 19)ans++;
  if(K == 23)ans++;
  vector<ll> fact,inv,fact_inv;
  auto fact_init = [&fact, &inv, &fact_inv](int N,ll mod){
    fact.resize(N+5);
    fact_inv.resize(N+5);
    inv.resize(N+5);
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < N+5; i++){
      fact[i] = fact[i-1] * i % mod;
      inv[i] = mod - inv[mod%i] * (mod/i) % mod;
      fact_inv[i] = fact_inv[i-1] * inv[i] % mod;
    }
  };
  auto comb = [&fact, &inv, &fact_inv](int N,int K,ll mod){
    return fact[N] * (fact_inv[K] * fact_inv[N-K] % mod) %mod;
  };
  fact_init(200,mod1);
  vector<vector<int>> com(25,vector<int>(25));
  REP(i,0,25){
    REP(j,0,25){
      com[i][j] = comb(i,j,mod1);
    }
  }
  const unsigned short b = 55440;
  ll p = 1; // 通りの数
  unsigned short v = 0; // 値の合計
  short k = K; // まだ配られていない人数
  function<void(short)> f = [&](short i){
    // cout << "i " << i << endl;
    // cout << "p " << p << endl;
    // cout << "v " << v << " " << (double)v/b << endl;
    // cout << "k " << k << endl;
    if((v == b) && (k == 0)){
      ans += p;
      return;
    }
    if(i == N+1){
      return;
    }
    if(i == 13){f(i+1); return;}
    if(i == 17){f(i+1); return;}
    if(i == 19){f(i+1); return;}
    if(i == 23){f(i+1); return;}
    if(v + k*(b/i) < b){
      return;
    }
    REP(j,(short)0,K+1){
      if(v + j*(b/i) > b){
        break;
      }
      if(k - j < 0){
        break;
      }
      p *= com[k][j];
      k -= j;
      v += j*(b/i);
      f(i+1);
      v -= j*(b/i);
      k += j;
      p /= com[k][j];
    }
    return;
  };
  f(1);
  cout << ans << '\n';
}
0