#1003480 (C++17(gcc12)) No.2846 Birthday Cake

• 問題: No.2846 Birthday Cake
• ユーザー: GOTKAKO
• 提出日時: 2024-08-23 23:08:22
• 言語: C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 5,034 bytes
• コンパイル時間: 6,720 ms
• コンパイル使用メモリ: 254,396 KB
• 最終ジャッジ日時: 2025-02-24 00:14:39
• ジャッジサーバーID （参考情報）: judge3 / judge4

コンパイルメッセージ

In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/x86_64-pc-linux-gnu/bits/stdc++.h:84,
                 from main.cpp:1:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/numeric: In instantiation of 'constexpr std::common_type_t<_Tp1, _Tp2> std::gcd(_Mn, _Nn) [with _Mn = int; _Nn = __int128; common_type_t<_Tp1, _Tp2> = __int128]':
main.cpp:128:32:   required from here
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/numeric:166:43: error: static assertion failed: std::gcd arguments must be integers
  166 |       static_assert(is_integral_v<_Mn> && is_integral_v<_Nn>,
      |                                           ^~~~~~~~~~~~~~~~~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/numeric:166:43: note: 'std::is_integral_v<__int128>' evaluates to false
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_pair.h:60,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_algobase.h:64,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/specfun.h:45,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/cmath:1935,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/x86_64-pc-linux-gnu/bits/stdc++.h:41:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/type_traits: In instantiation of 'struct std::make_unsigned<__int128>':
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/type_traits:2003:11:   required by substitution of 'template<class _Tp> using make_unsigned_t = typename std::make_unsigned::type [with _Tp = __int128]'
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/numeric:173:24:   required from 'constexpr std::common_type_t<_Tp1, _Tp2> std::gcd(_Mn, _Nn) [with _Mn = int; _Nn = __int128; common_type_t<_Tp1, _Tp2> = __int128]'
main.cpp:128:32:   required from here
/ho

ソースコード

#include <bits/stdc++.h>
using namespace std;

struct frac{ //最終的に分子分母64bitに収まる計算のみ.
    public:
    long long n,d;
    frac() : n(0),d(1){}
    frac(long long v) : n(v),d(1) {}
    frac(long long a,long long b,bool redu = true){
        assert(b != 0);
        if(redu) reduce(a,b);
        n = a,d = b; 
    }
    private:
    long long gcd(long long a,long long b){
        if(a%b == 0) return b;
        return gcd(b,a%b);
    } 
    long long gcd128(long long a,long long b){ //絶対値gcd128.
        if(b == 0) return abs(a);
        return gcd(abs(a),abs(b));
    }
    void reduce(long long &a,long long &b){ //約分.
        if(b < 0) a = -a,b = -b;
        long long div = gcd128(a,b);
        a /= div; b /= div;
    }
    public:
    //計算量 O(logmax(d,b.d)).
    friend frac operator+(const frac &b){return b;}
    friend frac operator-(const frac &b){return frac(-b.n,b.d,false);}
    friend frac operator+(const frac &a,const frac &b){
        return frac((long long)a.n*b.d+(long long)b.n*a.d,(long long)a.d*b.d);
    } 
    friend frac operator-(const frac &a,const frac &b){
        return frac((long long)a.n*b.d-(long long)b.n*a.d,(long long)a.d*b.d);
    }
    friend frac operator*(const frac &a,const frac &b){
        long long g1 = std::gcd(a.n,b.d),g2 = std::gcd(a.d,b.n);
        return frac((a.n/g1)*(b.n/g2),(a.d/g2)*(b.d/g1),false);
    }
    friend frac operator/(const frac &a,const frac &b){
        assert(b.n != 0);
        long long g1 = std::gcd(a.n,b.n),g2 = std::gcd(a.d,b.d);
        if(b.n < 0) return frac((-a.n/g1)*(b.d/g2),(a.d/g2)*(-b.n/g1));
        else return frac((a.n/g1)*(b.d/g2),(a.d/g2)*(b.n/g1));
    }
    friend bool operator==(const frac &a,const frac &b){return a.n==b.n && a.d==b.d;}
    friend bool operator!=(const frac &a,const frac &b){return a.n!=b.n || a.d!=b.d;}
    friend bool operator>(const frac &a,const frac &b){return (long long)a.n*b.d > (long long)b.n*a.d;}
    friend bool operator>=(const frac &a,const frac &b){return (long long)a.n*b.d >= (long long)b.n*a.d;}
    friend bool operator<(const frac &a,const frac &b){return (long long)a.n*b.d < (long long)b.n*a.d;}
    friend bool operator<=(const frac &a,const frac &b){return (long long)a.n*b.d <= (long long)b.n*a.d;}
 
    frac &operator=(const frac &b) = default;
    frac operator+=(const frac &b){return *this=*this+b;}
    frac operator-=(const frac &b){return *this=*this-b;}
    frac operator*=(const frac &b){return *this=*this*b;}
    frac operator/=(const frac &b){return *this=*this/b;}
    frac operator++(int){*this += frac(1); return *this;}
    frac operator--(int){*this -= frac(1); return *this;}
 
    double decimal(){return (n+0.0)/d;}
    long double decimall(){return ((long double)n)/d;}
    long long num(){return n;} long long den(){return d;}
    long long floor(){return n<0?(n+1)/d-1:n/d;}
    long long ceil(){return n>0?(n-1)/d+1:n/d;}
    frac inv(){return frac(n>=0?d:-d,n>=0?n:-n,false);}
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int K,N; cin >> K >> N;
    vector<__int128_t> fac(K+1);
    fac.at(0) = 1;
    for(int i=1; i<=K; i++) fac.at(i) = fac.at(i-1)*i;
    vector<frac> mindec(K+1);
    for(int i=1; i<=K; i++) mindec.at(i) = frac(i,N);

    vector<long long> lcm(N+1);
    long long lc = 1;
    for(int i=N; i>=1; i--) lc = lc*i/gcd(lc,i),lcm.at(i) = lc;

    long long inf = 1000000000;
    int left = N/2,right = (N-left);
    vector<unordered_map<long long,__int128_t>> dp1(K+1),dp2(K+1);
    dp1.at(0)[inf+1] += fac.at(K); dp2.at(0)[inf+1] += fac.at(K);

    for(int i=1; i<=left; i++){
        frac dec(1,i);
        for(int k=K-1; k>=0; k--){
            for(auto &[ke,v] : dp1.at(k)){
                frac now(ke/inf,ke%inf);
                for(int l=1; l<=K-k; l++){
                    now -= dec;
                    if(now < 0 || now.d > 20000) break;
                    dp1.at(k+l)[now.n*inf+now.d] += v/fac.at(l);
                }
            }
        }
    }
    for(int i=left+1; i<=N; i++){
        frac dec(1,i);
        for(int k=K-1; k>=0; k--){
            for(auto &[ke,v] : dp2.at(k)){
                frac now(ke/inf,ke%inf);
                for(int l=1; l<=K-k; l++){
                    now -= dec;
                    if(now < 0 || now.d > 20000) break;
                    dp2.at(k+l)[now.n*inf+now.d] += v/fac.at(l);
                }
            }
        }
    }
    
    long long answer = 0;
    for(int i=0; i<=K; i++){
        for(auto &[ke,v] : dp1.at(i)){
            frac now(ke/inf,ke%inf);
            now = frac(1)-now;
            auto itr = dp2.at(K-i).find(now.n*inf+now.d);
            if(itr != dp2.at(K-i).end()){
                __int128_t v2 = itr->second;
                for(int k=1; k<=K; k++){
                    int div = k;
                    int g = gcd(div,v);
                    div /= g; v /= g; v2 /= div;
                }
                answer += v*v2;
            }
        }
    }
    cout << answer << endl;
}