結果

問題 No.2846 Birthday Cake
コンテスト
ユーザー 已经死了
提出日時 2025-06-19 13:55:11
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 972 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,365 ms
コンパイル使用メモリ 194,000 KB
実行使用メモリ 16,068 KB
最終ジャッジ日時 2025-06-19 13:55:17
合計ジャッジ時間 5,915 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1
other -- * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int K,N;
i64 ans;
i64 cnt[25];
__int128 fact[25];
__int128 gcd128(__int128 a,__int128 b){return b?gcd128(b,a%b):a;}
void dfs(int i,int l,__int128 num,__int128 den){
    if(i==K){
        if(num==0){
            __int128 t=fact[K];
            for(int d=1;d<=N;++d) if(cnt[d]>1) t/=fact[cnt[d]];
            ans+=(i64)t;
        }
        return;
    }
    if(num*l>den*(K-i)) return;
    if(num*N<den*(K-i)) return;
    __int128 m=(den+num-1)/num;
    if(m> N) return;
    int s = l>(i64)m?l:(i64)m;
    for(int d=s;d<=N;++d){
        __int128 nnum = num*d - den;
        __int128 nden = den*d;
        __int128 g = gcd128(nnum,nden);
        cnt[d]++;
        dfs(i+1,d,nnum/g,nden/g);
        cnt[d]--;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>K>>N;
    fact[0]=1;
    for(int i=1;i<=K;++i) fact[i]=fact[i-1]*i;
    dfs(0,1,1,1);
    cout<<ans;
    return 0;
}
0