結果
問題 | No.1408 Nice Dice Game |
ユーザー |
![]() |
提出日時 | 2020-11-28 19:50:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 377 ms / 2,000 ms |
コード長 | 22,098 bytes |
コンパイル時間 | 2,432 ms |
コンパイル使用メモリ | 202,104 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-13 02:37:41 |
合計ジャッジ時間 | 18,038 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 36 |
ソースコード
////////////////////////////////////////////////////////////////////////////////// Give me AC!!! //////////////////////////////////////////////////////////////////////////////////#include <bits/stdc++.h>#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")using namespace std;using ll = long long;using ld = long double;using graph = vector<vector<int>>;#define REP(i,n) for(ll i=0;i<(ll)(n);i++)#define REPD(i,n) for(ll i=n-1;i>=0;i--)#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)//xにはvectorなどのコンテナ#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく#define MAX(x) *max_element(ALL(x)) //最大値を求める#define MIN(x) *min_element(ALL(x)) //最小値を求める#define PQ priority_queue<vector<ll>,vector<vector<ll>>,greater<vector<ll>>>#define PB push_back //vectorヘの挿入#define MP make_pair //pairのコンストラクタ#define S second //pairの二つ目の要素#define coutY cout<<"YES"<<endl#define couty cout<<"Yes"<<endl#define coutN cout<<"NO"<<endl#define coutn cout<<"No"<<endl#define coutdouble(a,b) cout << fixed << setprecision(a) << double(b) ;#define vi(a,b) vector<int> a(b)#define vl(a,b) vector<ll> a(b)#define vs(a,b) vector<string> a(b)#define vll(a,b,c) vector<vector<ll>> a(b, vector<ll>(c));#define intque(a) queue<int> a;#define llque(a) queue<ll> a;#define intque2(a) priority_queue<int, vector<int>, greater<int>> a;#define llque2(a) priority_queue<ll, vector<ll>, greater<ll>> a;#define pushback(a,b) a.push_back(b)#define mapii(M1) map<int, int> M1;#define cou(v,x) count(v.begin(), v.end(), x)#define mapll(M1) map<ll,ll> M1;#define mapls(M1) map<ll, string> M1;#define mapsl(M1) map<string, ll> M1;#define twolook(a,l,r,x) lower_bound(a+l, a+r, x) - a#define sor(a) sort(a.begin(), a.end())#define rever(a) reverse(a.begin(),a.end())#define rep(i,a) for(ll i=0;i<a;i++)#define vcin(n) for(ll i=0;i<ll(n.size());i++) cin>>n[i]#define vcout(n) for(ll i=0;i<ll(n.size());i++) cout<<n[i]#define vcin2(n) rep(i,ll(n.size())) rep(j,ll(n.at(0).size())) cin>>n[i][j]const ll mod = 998244353;const ll MOD = 998244353;//const ll MOD = 1000000007;//const ll mod = 1000000007;constexpr ll MAX = 5000000;//const ll _max = 9223372036854775807;const ll _max = 1223372036854775807;const ll INF = 2000000000000000000;static const long double pi = 3.141592653589793;const int MAX_COL=350;const int MAX_ROW=350;ll fac[MAX],finv[MAX],inv[MAX];// テーブルを作る前処理void COMinit() {fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (int i = 2; i < MAX; i++){fac[i] = fac[i - 1] * i % MOD;inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;finv[i] = finv[i - 1] * inv[i] % MOD;}}// 二項係数計算long long COM(int n, int k){if (n < k) return 0;if (n < 0 || k < 0) return 0;return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;}int modPow(long long a, long long n, long long p) {if (a == 0 && n == 0) return 0;if (n == 0) return 1; // 0乗にも対応する場合if (n == 1) return a % p;if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p;long long t = modPow(a, n / 2, p);return (t * t) % p;}ll clocks(ll a,ll b,ll c){return a*3600+b*60+c;}ll divup(ll b,ll d){if(b%d==0){return b/d;}else{return b/d+1;}}struct edge {int to; // 辺の行き先int weight; // 辺の重みedge(int t, int w) : to(t), weight(w) { }};using Graphw = vector<vector<edge>>;ll zero(ll a){return max(ll(0),a);}template< typename T >struct FormalPowerSeries : vector< T > {using vector< T >::vector;using P = FormalPowerSeries;using MULT = function< P(P, P) >;static MULT &get_mult() {static MULT mult = nullptr;return mult;}static void set_fft(MULT f) {get_mult() = f;}void shrink() {while(this->size() && this->back() == T(0)) this->pop_back();}P operator+(const P &r) const { return P(*this) += r; }P operator+(const T &v) const { return P(*this) += v; }P operator-(const P &r) const { return P(*this) -= r; }P operator-(const T &v) const { return P(*this) -= v; }P operator*(const P &r) const { return P(*this) *= r; }P operator*(const T &v) const { return P(*this) *= v; }P operator/(const P &r) const { return P(*this) /= r; }P operator%(const P &r) const { return P(*this) %= r; }P &operator+=(const P &r) {if(r.size() > this->size()) this->resize(r.size());for(int i = 0; i < r.size(); i++) (*this)[i] += r[i];return *this;}P &operator+=(const T &r) {if(this->empty()) this->resize(1);(*this)[0] += r;return *this;}P &operator-=(const P &r) {if(r.size() > this->size()) this->resize(r.size());for(int i = 0; i < r.size(); i++) (*this)[i] -= r[i];shrink();return *this;}P &operator-=(const T &r) {if(this->empty()) this->resize(1);(*this)[0] -= r;shrink();return *this;}P &operator*=(const T &v) {const int n = (int) this->size();for(int k = 0; k < n; k++) (*this)[k] *= v;return *this;}P &operator*=(const P &r) {if(this->empty() || r.empty()) {this->clear();return *this;}assert(get_mult() != nullptr);return *this = get_mult()(*this, r);}P &operator%=(const P &r) {return *this -= *this / r * r;}P operator-() const {P ret(this->size());for(int i = 0; i < this->size(); i++) ret[i] = -(*this)[i];return ret;}P &operator/=(const P &r) {if(this->size() < r.size()) {this->clear();return *this;}int n = this->size() - r.size() + 1;return *this = (rev().pre(n) * r.rev().inv(n)).pre(n).rev(n);}P pre(int sz) const {return P(begin(*this), begin(*this) + min((int) this->size(), sz));}P operator>>(int sz) const {if(this->size() <= sz) return {};P ret(*this);ret.erase(ret.begin(), ret.begin() + sz);return ret;}P operator<<(int sz) const {P ret(*this);ret.insert(ret.begin(), sz, T(0));return ret;}P rev(int deg = -1) const {P ret(*this);if(deg != -1) ret.resize(deg, T(0));reverse(begin(ret), end(ret));return ret;}P diff() const {const int n = (int) this->size();P ret(max(0, n - 1));for(int i = 1; i < n; i++) ret[i - 1] = (*this)[i] * T(i);return ret;}P integral() const {const int n = (int) this->size();P ret(n + 1);ret[0] = T(0);for(int i = 0; i < n; i++) ret[i + 1] = (*this)[i] / T(i + 1);return ret;}// F(0) must not be 0P inv(int deg = -1) const {assert(((*this)[0]) != T(0));const int n = (int) this->size();if(deg == -1) deg = n;P ret({T(1) / (*this)[0]});for(int i = 1; i < deg; i <<= 1) {ret = (ret + ret - ret * ret * pre(i << 1)).pre(i << 1);}return ret.pre(deg);}// F(0) must be 1P log(int deg = -1) const {assert((*this)[0] == 1);const int n = (int) this->size();if(deg == -1) deg = n;return (this->diff() * this->inv(deg)).pre(deg - 1).integral();}P sqrt(int deg = -1) const {const int n = (int) this->size();if(deg == -1) deg = n;if((*this)[0] == T(0)) {for(int i = 1; i < n; i++) {if((*this)[i] != T(0)) {if(i & 1) return {};if(deg - i / 2 <= 0) break;auto ret = (*this >> i).sqrt(deg - i / 2) << (i / 2);if(ret.size() < deg) ret.resize(deg, T(0));return ret;}}return P(deg, 0);}P ret({T(1)});T inv2 = T(1) / T(2);for(int i = 1; i < deg; i <<= 1) {ret = (ret + pre(i << 1) * ret.inv(i << 1)) * inv2;}return ret.pre(deg);}// F(0) must be 0P exp(int deg = -1) const {assert((*this)[0] == T(0));const int n = (int) this->size();if(deg == -1) deg = n;P ret({T(1)});for(int i = 1; i < deg; i <<= 1) {ret = (ret * (pre(i << 1) + T(1) - ret.log(i << 1))).pre(i << 1);}return ret.pre(deg);}P pow(int64_t k, int deg = -1) const {const int n = (int) this->size();if(deg == -1) deg = n;for(int i = 0; i < n; i++) {if((*this)[i] != T(0)) {T rev = T(1) / (*this)[i];P C(*this * rev);P D(n - i);for(int j = i; j < n; j++) D[j - i] = C[j];D = (D.log() * k).exp() * (*this)[i].pow(k);P E(deg);if(i * k > deg) return E;auto S = i * k;for(int j = 0; j + S < deg && j < D.size(); j++) E[j + S] = D[j];return E;}}return *this;}T eval(T x) const {T r = 0, w = 1;for(auto &v : *this) {r += w * v;w *= x;}return r;}};//aはbの何乗以下かを満たす数の内最大の物,(a,10)はaの桁数ll expless(ll a,ll b){ll k=0;ll o=1;while(a>=o){k++;o=o*b;}return k;}//aをb進法で表す//b進法のaを10進法に直すll tenbase(ll a,ll b){ll c=expless(a,10);ll ans=0;ll k=1;for(int i=0;i<c;i++){ans+=(a%10)*k;k=k*b;a=a/10;}return ans;}vector<pair<long long, long long> > prime_factorize(long long N) {vector<pair<long long, long long> > res;for (long long a = 2; a * a <= N; ++a) {if (N % a != 0) continue;long long ex = 0; // 指数// 割れる限り割り続けるwhile (N % a == 0) {++ex;N /= a;}// その結果を pushres.push_back({a, ex});}// 最後に残った数についてif (N != 1) res.push_back({N, 1});return res;}//aがbで何回割り切るかll exp(ll a,ll b){ll ans=0;while(a%b==0){a=a/b;ans++;}return ans;}const int dx[4] = {1, 0, -1, 0};const int dy[4] = {0, 1, 0, -1};const int X[6]={1,1,0,-1,-1,0};const int Y[6]={0,1,1,0,-1,-1};template<typename T>vector<T> smallest_prime_factors(T n) {vector<T> spf(n + 1);for (int i = 0; i <= n; i++) spf[i] = i;for (T i = 2; i * i <= n; i++) {// 素数だったらif (spf[i] == i) {for (T j = i * i; j <= n; j += i) {// iを持つ整数かつまだ素数が決まっていないならif (spf[j] == j) {spf[j] = i;}}}}return spf;}vector<pair<ll,ll>> factolization(ll x, vector<ll> &spf) {vector<pair<ll,ll>> ret;ll p;ll z;while (x != 1) {p=(spf[x]);z=0;while(x%p==0){z++;x /= p;}ret.push_back({p, z});}return ret;}vector<bool> is;vector<long long int> prime_(ll n){is.resize(n+1, true);is[0] = false;is[1] = false;vector<long long int> primes;for (int i=2; i<=n; i++) {if (is[i] == true){primes.push_back(i);for (int j=i*2; j<=n; j+=i){is[j] = false;}}}return primes;}vector<ll> dijkstra(ll f,ll n,vector<vector<vector<ll>>>& edge){//最短経路としてどの頂点が確定済みかをチェックする配列vector<ll> confirm(n,false);//それぞれの頂点への最短距離を保存する配列//始点は0,始点以外はINFで最短距離を初期化するvector<ll> mincost(n,INF);mincost[f]=0;//確定済みの頂点の集合から伸びる辺を伝ってたどり着く頂点の始点からの距離を短い順に保存するPriority queuePQ mincand;mincand.push({mincost[f],f});//mincandの要素がゼロの時、最短距離を更新できる頂点がないことを示すwhile(!mincand.empty()){//最短距離でたどり着くと思われる頂点を取り出すvector<ll> next=mincand.top();mincand.pop();//すでにその頂点への最短距離が確定済みの場合は飛ばすif(confirm[next[1]]) continue;//確定済みではない場合は確定済みにするconfirm[next[1]]=true;//その確定済みの頂点から伸びる辺の情報をとってくる(参照の方が速い)、lは辺の本数vector<vector<ll>>& v=edge[next[1]];ll l=SIZE(v);REP(i,l){//辺の先が確定済みなら更新する必要がない((✳︎2)があれば十分なので(✳︎1)は実はいらない)if(confirm[v[i][0]]) continue; //(✳︎1)//辺の先のmincost以上の場合は更新する必要がない(辺の先が確定済みの時は満たす)if(mincost[v[i][0]]<=next[0]+v[i][1]) continue; //(✳︎2)//更新mincost[v[i][0]]=next[0]+v[i][1];//更新した場合はその頂点が(確定済みでない頂点の中で)最短距離になる可能性があるのでmincandに挿入mincand.push({mincost[v[i][0]],v[i][0]});}}return mincost;}ll so(ll a){ll ans=0;if(a==0){return 0;}while(a%2==0){a/=2;ans++;}return ans;}ll HOM(ll n,ll r){return COM(n+r-1,r);}ll binary(ll bina){ll ans = 0;for (ll i = 0; bina>0 ; i++){ans = ans+(bina%2)*pow(10,i);bina = bina/2;}return ans;}vector<long long> enum_divisors(long long N) {vector<long long> res;for (long long i = 1; i * i <= N; ++i) {if (N % i == 0) {res.push_back(i);// 重複しないならば i の相方である N/i も pushif (N/i != i) res.push_back(N/i);}}// 小さい順に並び替えるsort(res.begin(), res.end());return res;}vector<ll> zaatu(vector<ll> a,ll n){map<ll,ll> mp;for (int i = 0; i < n; i++) {cin >> a[i];mp[a[i]] = 0;}// 小さい値から順に番号を付けていくll num = 0;for (auto x : mp) {mp[x.first] = num;num++;}vector<ll> ans;for(int i=0;i<n;i++){ans.push_back(mp[a[i]]);}return ans;}ll vectorcheck(vector<ll> t,ll key){auto iter = lower_bound(ALL(t), key);auto iter2 = upper_bound(ALL(t), key);if((iter-t.begin())!=(iter2-t.begin())){return 1;}else{return 0;}}template<class Monoid>struct SegmentTree {using T = typename Monoid::value_type;std::vector<T> tree;SegmentTree() = default;explicit SegmentTree(ll n):tree(n << 1, Monoid::identity()) {};template<class InputIterator>SegmentTree(InputIterator first, InputIterator last) {tree.assign(distance(first, last) << 1, Monoid::identity());ll i;i = size();for (InputIterator itr = first; itr != last; itr++) {tree[i++] = *itr;}for (i = size() - 1; i > 0; i--) {tree[i] = Monoid::operation(tree[(i << 1)], tree[(i << 1) | 1]);}};inline ll size() {return tree.size() >> 1;};inline T operator[] (ll k) {return tree[k + size()];};void add(ll k, const T dat) {k += size();tree[k] += dat;while(k > 1) {k >>= 1;tree[k] = Monoid::operation(tree[(k << 1)], tree[(k << 1) | 1]);}};void update(ll k, const T dat) {k += size();tree[k] = dat;while(k > 1) {k >>= 1;tree[k] = Monoid::operation(tree[(k << 1)], tree[(k << 1) | 1]);}};T fold(ll l, ll r) {l += size(); //points leafr += size();T lv = Monoid::identity();T rv = Monoid::identity();while (l < r) {if (l & 1) lv = Monoid::operation(lv, tree[l++]);if (r & 1) rv = Monoid::operation(tree[--r], rv);l >>= 1;r >>= 1;}return Monoid::operation(lv, rv);};template<class F>inline ll sub_tree_search(ll i, T sum, F f) {while (i < size()) {T x = Monoid::operation(sum, tree[i << 1]);if (f(x)) {i = i << 1;}else {sum = x;i = (i << 1) | 1;}}return i - size();}template<class F>ll search(ll l, F f) {l += size();ll r = size() * 2; //r = n;ll tmpr = r;ll shift = 0;T sum = Monoid::identity();while (l < r) {if (l & 1) {if (f(Monoid::operation(sum, tree[l]))) {return sub_tree_search(l, sum, f);}sum = Monoid::operation(sum, tree[l]);l++;}l >>= 1;r >>= 1;shift++;}while (shift > 0) {shift--;r = tmpr >> shift;if (r & 1) {r--;if (f(Monoid::operation(sum, tree[r]))) {return sub_tree_search(r, sum, f);}sum = Monoid::operation(sum, tree[r]);}}return -1;};};using namespace std;using llong = long long;struct Monoid {using value_type = ll;inline static ll identity() {return 0;};inline static ll operation(ll a, ll b) {return a+b;};};class mint {long long x;public:mint(long long x=0) : x((x%mod+mod)%mod) {}mint operator-() const {return mint(-x);}mint& operator+=(const mint& a) {if ((x += a.x) >= mod) x -= mod;return *this;}mint& operator-=(const mint& a) {if ((x += mod-a.x) >= mod) x -= mod;return *this;}mint& operator*=(const mint& a) {(x *= a.x) %= mod;return *this;}mint operator+(const mint& a) const {mint res(*this);return res+=a;}mint operator-(const mint& a) const {mint res(*this);return res-=a;}mint operator*(const mint& a) const {mint res(*this);return res*=a;}mint pow(ll t) const {if (!t) return 1;mint a = pow(t>>1);a *= a;if (t&1) a *= *this;return a;}// for prime modmint inv() const {return pow(mod-2);}mint& operator/=(const mint& a) {return (*this) *= a.inv();}mint operator/(const mint& a) const {mint res(*this);return res/=a;}friend ostream& operator<<(ostream& os, const mint& m){os << m.x;return os;}};int ctoi(const char c){switch(c){case '0': return 0;case '1': return 1;case '2': return 2;case '3': return 3;case '4': return 4;case '5': return 5;case '6': return 6;case '7': return 7;case '8': return 8;case '9': return 9;default : return -1;}}ll ord(ll a,ll b){ll ans=0;while(a%b==0){ans++;a/=b;}return ans;}ll atll(ll a,ll b){b++;ll c=expless(a,10);ll d=c-b;ll f=1;for(int i=0;i<d;i++){f=f*10;}a=(a/f);return a%10;}class UnionFind {public:vector <ll> par; // 各元の親を表す配列vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)// ConstructorUnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身}void init(ll sz_) {par.resize(sz_);siz.assign(sz_, 1LL); // resize だとなぜか初期化されなかったfor (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身}// Member Function// Findll root(ll x) { // 根の検索while (par[x] != x) {x = par[x] = par[par[x]]; // x の親の親を x の親とする}return x;}// Union(Unite, Merge)bool merge(ll x, ll y) {x = root(x);y = root(y);if (x == y) return false;// merge technique(データ構造をマージするテク.小を大にくっつける)if (siz[x] < siz[y]) swap(x, y);siz[x] += siz[y];par[y] = x;return true;}bool issame(ll x, ll y) { // 連結判定return root(x) == root(y);}ll size(ll x) { // 素集合のサイズreturn siz[root(x)];}};struct BitMatrix {int H, W;bitset<MAX_COL> val[MAX_ROW];BitMatrix(int m = 1, int n = 1) : H(m), W(n) {}inline bitset<MAX_COL>& operator [] (int i) {return val[i];}};int GaussJordan(BitMatrix &A, bool is_extended = false) {int rank = 0;for (int col = 0; col < A.W; ++col) {if (is_extended && col == A.W - 1) break;int pivot = -1;for (int row = rank; row < A.H; ++row) {if (A[row][col]) {pivot = row;break;}}if (pivot == -1) continue;swap(A[pivot], A[rank]);for (int row = 0; row < A.H; ++row) {if (row != rank && A[row][col]) A[row] ^= A[rank];}++rank;}return rank;}int pos(const char c){if('a' <= c && c <= 'z') return (c-'a');return -1;}ld zeta(ll a){ld ans=0;ll tmp=1;for(ll i=1;i<=100000000;i++){tmp=1;ll k=0;for(ll j=1;j<=a;j++){if(tmp>=1000000000000ll){k++;break;}tmp*=i;}if(k==0){ans+=ld(1)/ld(tmp);}// cout<<tmp<<endl;}return ans;}ll x[4]={1,0,-1,0};ll y[4]={0,1,0,-1};int main() {ios::sync_with_stdio(false);std::cin.tie(nullptr);cout << fixed << setprecision(30);ll a;cin>>a;a+=2;cout<<zeta(a)<<endl;}