結果
問題 |
No.2846 Birthday Cake
|
ユーザー |
|
提出日時 | 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 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
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; }