結果

問題 No.2846 Birthday Cake
コンテスト
ユーザー Andrew8128
提出日時 2024-08-23 23:25:24
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,397 bytes
コンパイル時間 5,505 ms
コンパイル使用メモリ 311,576 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-08-23 23:25:57
合計ジャッジ時間 32,532 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27 TLE * 7
権限があれば一括ダウンロードができます

ソースコード

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);
  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 *= 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