結果

問題 No.2846 Birthday Cake
ユーザー Andrew8128Andrew8128
提出日時 2024-08-23 23:16:07
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,356 bytes
コンパイル時間 5,008 ms
コンパイル使用メモリ 309,956 KB
実行使用メモリ 13,752 KB
最終ジャッジ日時 2024-08-23 23:16:30
合計ジャッジ時間 21,002 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
13,752 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 1,472 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 3 ms
6,944 KB
testcase_05 AC 1,950 ms
6,944 KB
testcase_06 TLE -
testcase_07 TLE -
testcase_08 TLE -
testcase_09 TLE -
testcase_10 TLE -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
権限があれば一括ダウンロードができます

ソースコード

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);
  int 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(20000,mod1);
  int b = 55440;
  ll p = 1; // 通りの数
  int v = 0; // 値の合計
  int k = K; // まだ配られていない人数
  function<void(int)> f = [&](int 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,0,K+1){
      if(v + j*(b/i) > b){
        break;
      }
      if(k - j < 0){
        break;
      }
      p *= comb(k,j,mod1);
      k -= j;
      v += j*(b/i);
      f(i+1);
      v -= j*(b/i);
      k += j;
      p /= comb(k,j,mod1);
    }
    return;
  };
  f(1);
  cout << ans << '\n';
}
0