結果
| 問題 | No.1073 無限すごろく |
| ユーザー |
 apricity
|
| 提出日時 | 2023-02-12 03:14:01 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 17,263 bytes |
| コンパイル時間 | 1,297 ms |
| コンパイル使用メモリ | 126,884 KB |
| 最終ジャッジ日時 | 2025-02-10 14:39:13 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge4 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp:429:30: error: ‘function’ does not name a type; did you mean ‘union’?
429 | P sqrt(int deg = -1, const function< T(T) > &get_sqrt = [](T) { return T(1); }) const {
| ^~~~~~~~
| union
main.cpp:429:38: error: expected ‘,’ or ‘...’ before ‘<’ token
429 | P sqrt(int deg = -1, const function< T(T) > &get_sqrt = [](T) { return T(1); }) const {
| ^
main.cpp:456:16: error: ‘function’ does not name a type; did you mean ‘union’?
456 | P sqrt(const function< T(T) > &get_sqrt, int deg = -1) const {
| ^~~~~~~~
| union
main.cpp:456:24: error: expected ‘,’ or ‘...’ before ‘<’ token
456 | P sqrt(const function< T(T) > &get_sqrt, int deg = -1) const {
| ^
main.cpp:429:24: error: default argument missing for parameter 2 of ‘FormalPowerSeries<T>::P FormalPowerSeries<T>::sqrt(int, int) const’
429 | P sqrt(int deg = -1, const function< T(T) > &get_sqrt = [](T) { return T(1); }) const {
| ^~~~~~~~~~~~~~
main.cpp:429:14: note: ...following parameter 1 which has a default argument
429 | P sqrt(int deg = -1, const function< T(T) > &get_sqrt = [](T) { return T(1); }) const {
| ~~~~^~~~~~~~
main.cpp: In member function ‘FormalPowerSeries<T>::P FormalPowerSeries<T>::sqrt(int, int) const’:
main.cpp:437:53: error: ‘get_sqrt’ was not declared in this scope
437 | auto ret = (*this >> i).sqrt(deg - i / 2, get_sqrt);
| ^~~~~~~~
main.cpp: In member function ‘FormalPowerSeries<T>::P FormalPowerSeries<T>::sqrt(int) const’:
main.cpp:457:17: error: ‘deg’ was not declared in this scope
457 | return sqrt(deg, get_sqrt);
| ^~~
main.cpp:457:22: error: ‘get_sqrt’ was not declared in this scope
ソースコード
#include<iostream>#include<string>#include<vector>#include<algorithm>#include<numeric>#include<cmath>#include<utility>#include<tuple>#include<cstdint>#include<cstdio>#include<iomanip>#include<map>#include<queue>#include<set>#include<stack>#include<deque>#include<unordered_map>#include<unordered_set>#include<bitset>#include<cctype>#include<chrono>#include<random>#include<cassert>#include<cstddef>#include<iterator>#include<string_view>#include<type_traits>#ifdef LOCAL# include "debug_print.hpp"# define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)#else# define debug(...) (static_cast<void>(0))#endifusing namespace std;#define rep(i,n) for(int i=0; i<(n); i++)#define rrep(i,n) for(int i=(n)-1; i>=0; i--)#define FOR(i,a,b) for(int i=(a); i<(b); i++)#define RFOR(i,a,b) for(int i=(b-1); i>=(a); i--)#define ALL(v) v.begin(), v.end()#define RALL(v) v.rbegin(), v.rend()#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );#define pb push_backusing ll = long long;using D = double;using LD = long double;using P = pair<int, int>;template<typename T> using PQ = priority_queue<T,vector<T>>;template<typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }void yesno(bool flag) {cout << (flag?"Yes":"No") << "\n";}template<typename T, typename U>ostream &operator<<(ostream &os, const pair<T, U> &p) {os << p.first << " " << p.second;return os;}template<typename T, typename U>istream &operator>>(istream &is, pair<T, U> &p) {is >> p.first >> p.second;return is;}template<typename T>ostream &operator<<(ostream &os, const vector<T> &v) {int s = (int)v.size();for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i];return os;}template<typename T>istream &operator>>(istream &is, vector<T> &v) {for (auto &x : v) is >> x;return is;}void in() {}template<typename T, class... U>void in(T &t, U &...u) {cin >> t;in(u...);}void out() { cout << "\n"; }template<typename T, class... U, char sep = ' '>void out(const T &t, const U &...u) {cout << t;if (sizeof...(u)) cout << sep;out(u...);}void outr() {}template<typename T, class... U, char sep = ' '>void outr(const T &t, const U &...u) {cout << t;outr(u...);}namespace FastFourierTransform {using real = double;struct C {real x, y;C() : x(0), y(0) {}C(real x, real y) : x(x), y(y) {}inline C operator+(const C &c) const { return C(x + c.x, y + c.y); }inline C operator-(const C &c) const { return C(x - c.x, y - c.y); }inline C operator*(const C &c) const { return C(x * c.x - y * c.y, x * c.y + y * c.x); }inline C conj() const { return C(x, -y); }};const real PI = acosl(-1);int base = 1;vector< C > rts = { {0, 0},{1, 0} };vector< int > rev = {0, 1};void ensure_base(int nbase) {if(nbase <= base) return;rev.resize(1 << nbase);rts.resize(1 << nbase);for(int i = 0; i < (1 << nbase); i++) {rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1));}while(base < nbase) {real angle = PI * 2.0 / (1 << (base + 1));for(int i = 1 << (base - 1); i < (1 << base); i++) {rts[i << 1] = rts[i];real angle_i = angle * (2 * i + 1 - (1 << base));rts[(i << 1) + 1] = C(cos(angle_i), sin(angle_i));}++base;}}void fft(vector< C > &a, int n) {assert((n & (n - 1)) == 0);int zeros = __builtin_ctz(n);ensure_base(zeros);int shift = base - zeros;for(int i = 0; i < n; i++) {if(i < (rev[i] >> shift)) {swap(a[i], a[rev[i] >> shift]);}}for(int k = 1; k < n; k <<= 1) {for(int i = 0; i < n; i += 2 * k) {for(int j = 0; j < k; j++) {C z = a[i + j + k] * rts[j + k];a[i + j + k] = a[i + j] - z;a[i + j] = a[i + j] + z;}}}}vector< int64_t > multiply(const vector< int > &a, const vector< int > &b) {int need = (int) a.size() + (int) b.size() - 1;int nbase = 1;while((1 << nbase) < need) nbase++;ensure_base(nbase);int sz = 1 << nbase;vector< C > fa(sz);for(int i = 0; i < sz; i++) {int x = (i < (int) a.size() ? a[i] : 0);int y = (i < (int) b.size() ? b[i] : 0);fa[i] = C(x, y);}fft(fa, sz);C r(0, -0.25 / (sz >> 1)), s(0, 1), t(0.5, 0);for(int i = 0; i <= (sz >> 1); i++) {int j = (sz - i) & (sz - 1);C z = (fa[j] * fa[j] - (fa[i] * fa[i]).conj()) * r;fa[j] = (fa[i] * fa[i] - (fa[j] * fa[j]).conj()) * r;fa[i] = z;}for(int i = 0; i < (sz >> 1); i++) {C A0 = (fa[i] + fa[i + (sz >> 1)]) * t;C A1 = (fa[i] - fa[i + (sz >> 1)]) * t * rts[(sz >> 1) + i];fa[i] = A0 + A1 * s;}fft(fa, sz >> 1);vector< int64_t > ret(need);for(int i = 0; i < need; i++) {ret[i] = llround(i & 1 ? fa[i >> 1].y : fa[i >> 1].x);}return ret;}};/** @brief Arbitrary Mod Convolution(任意mod畳み込み)*/template< typename T >struct ArbitraryModConvolution {using real = FastFourierTransform::real;using C = FastFourierTransform::C;ArbitraryModConvolution() = default;static vector< T > multiply(const vector< T > &a, const vector< T > &b, int need = -1) {if(need == -1) need = a.size() + b.size() - 1;int nbase = 0;while((1 << nbase) < need) nbase++;FastFourierTransform::ensure_base(nbase);int sz = 1 << nbase;vector< C > fa(sz);for(int i = 0; i < a.size(); i++) {fa[i] = C(a[i].x & ((1 << 15) - 1), a[i].x >> 15);}fft(fa, sz);vector< C > fb(sz);if(a == b) {fb = fa;} else {for(int i = 0; i < b.size(); i++) {fb[i] = C(b[i].x & ((1 << 15) - 1), b[i].x >> 15);}fft(fb, sz);}real ratio = 0.25 / sz;C r2(0, -1), r3(ratio, 0), r4(0, -ratio), r5(0, 1);for(int i = 0; i <= (sz >> 1); i++) {int j = (sz - i) & (sz - 1);C a1 = (fa[i] + fa[j].conj());C a2 = (fa[i] - fa[j].conj()) * r2;C b1 = (fb[i] + fb[j].conj()) * r3;C b2 = (fb[i] - fb[j].conj()) * r4;if(i != j) {C c1 = (fa[j] + fa[i].conj());C c2 = (fa[j] - fa[i].conj()) * r2;C d1 = (fb[j] + fb[i].conj()) * r3;C d2 = (fb[j] - fb[i].conj()) * r4;fa[i] = c1 * d1 + c2 * d2 * r5;fb[i] = c1 * d2 + c2 * d1;}fa[j] = a1 * b1 + a2 * b2 * r5;fb[j] = a1 * b2 + a2 * b1;}fft(fa, sz);fft(fb, sz);vector< T > ret(need);for(int i = 0; i < need; i++) {int64_t aa = llround(fa[i].x);int64_t bb = llround(fb[i].x);int64_t cc = llround(fa[i].y);aa = T(aa).x, bb = T(bb).x, cc = T(cc).x;ret[i] = aa + (bb << 15) + (cc << 30);}return ret;}};/*** @brief Formal Power Series(形式的冪級数)*/template< typename T >struct FormalPowerSeries : vector< T > {using vector< T >::vector;using P = FormalPowerSeries;using Conv = ArbitraryModConvolution< T >;P pre(int deg) const {return P(begin(*this), begin(*this) + min((int) this->size(), deg));}P rev(int deg = -1) const {P ret(*this);if(deg != -1) ret.resize(deg, T(0));reverse(begin(ret), end(ret));return ret;}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 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;}// https://judge.yosupo.jp/problem/convolution_modP &operator*=(const P &r) {if(this->empty() || r.empty()) {this->clear();return *this;}auto ret = Conv::multiply(*this, r);return *this = {begin(ret), end(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 &operator%=(const P &r) {return *this -= *this / r * r;}// https://judge.yosupo.jp/problem/division_of_polynomialspair< P, P > div_mod(const P &r) {P q = *this / r;return make_pair(q, *this - q * 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 T &r) {if(this->empty()) this->resize(1);(*this)[0] += r;return *this;}P &operator-=(const T &r) {if(this->empty()) this->resize(1);(*this)[0] -= r;return *this;}P &operator*=(const T &v) {for(int i = 0; i < this->size(); i++) (*this)[i] *= v;return *this;}P dot(P r) const {P ret(min(this->size(), r.size()));for(int i = 0; i < ret.size(); i++) ret[i] = (*this)[i] * r[i];return ret;}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;}T operator()(T x) const {T r = 0, w = 1;for(auto &v : *this) {r += w * v;w *= x;}return r;}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;}// https://judge.yosupo.jp/problem/inv_of_formal_power_series// 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);}// https://judge.yosupo.jp/problem/log_of_formal_power_series// F(0) must be 1P log(int deg = -1) const {assert((*this)[0] == T(1));const int n = (int) this->size();if(deg == -1) deg = n;return (this->diff() * this->inv(deg)).pre(deg - 1).integral();}// https://judge.yosupo.jp/problem/sqrt_of_formal_power_seriesP sqrt(int deg = -1, const function< T(T) > &get_sqrt = [](T) { return T(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, get_sqrt);if(ret.empty()) return {};ret = ret << (i / 2);if(ret.size() < deg) ret.resize(deg, T(0));return ret;}}return P(deg, 0);}auto sqr = T(get_sqrt((*this)[0]));if(sqr * sqr != (*this)[0]) return {};P ret{sqr};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);}P sqrt(const function< T(T) > &get_sqrt, int deg = -1) const {return sqrt(deg, get_sqrt);}// https://judge.yosupo.jp/problem/exp_of_formal_power_series// F(0) must be 0P exp(int deg = -1) const {if(deg == -1) deg = this->size();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);}// https://judge.yosupo.jp/problem/pow_of_formal_power_seriesP 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 ret = (((*this * rev) >> i).log() * k).exp() * ((*this)[i].pow(k));if(i * k > deg) return P(deg, T(0));ret = (ret << (i * k)).pre(deg);if(ret.size() < deg) ret.resize(deg, T(0));return ret;}}return *this;}// https://yukicoder.me/problems/no/215P mod_pow(int64_t k, P g) const {P modinv = g.rev().inv();auto get_div = [&](P base) {if(base.size() < g.size()) {base.clear();return base;}int n = base.size() - g.size() + 1;return (base.rev().pre(n) * modinv.pre(n)).pre(n).rev(n);};P x(*this), ret{1};while(k > 0) {if(k & 1) {ret *= x;ret -= get_div(ret) * g;ret.shrink();}x *= x;x -= get_div(x) * g;x.shrink();k >>= 1;}return ret;}// https://judge.yosupo.jp/problem/polynomial_taylor_shiftP taylor_shift(T c) const {int n = (int) this->size();vector< T > fact(n), rfact(n);fact[0] = rfact[0] = T(1);for(int i = 1; i < n; i++) fact[i] = fact[i - 1] * T(i);rfact[n - 1] = T(1) / fact[n - 1];for(int i = n - 1; i > 1; i--) rfact[i - 1] = rfact[i] * T(i);P p(*this);for(int i = 0; i < n; i++) p[i] *= fact[i];p = p.rev();P bs(n, T(1));for(int i = 1; i < n; i++) bs[i] = bs[i - 1] * c * rfact[i] * fact[i - 1];p = (p * bs).pre(n);p = p.rev();for(int i = 0; i < n; i++) p[i] *= rfact[i];return p;}};template< int mod >struct ModInt {int x;ModInt() : x(0) {}ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}ModInt &operator+=(const ModInt &p) {if((x += p.x) >= mod) x -= mod;return *this;}ModInt &operator-=(const ModInt &p) {if((x += mod - p.x) >= mod) x -= mod;return *this;}ModInt &operator*=(const ModInt &p) {x = (int) (1LL * x * p.x % mod);return *this;}ModInt &operator/=(const ModInt &p) {*this *= p.inverse();return *this;}ModInt operator-() const { return ModInt(-x); }ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }bool operator==(const ModInt &p) const { return x == p.x; }bool operator!=(const ModInt &p) const { return x != p.x; }ModInt inverse() const {int a = x, b = mod, u = 1, v = 0, t;while(b > 0) {t = a / b;swap(a -= t * b, b);swap(u -= t * v, v);}return ModInt(u);}ModInt pow(int64_t n) const {ModInt ret(1), mul(x);while(n > 0) {if(n & 1) ret *= mul;mul *= mul;n >>= 1;}return ret;}friend ostream &operator<<(ostream &os, const ModInt &p) {return os << p.x;}friend istream &operator>>(istream &is, ModInt &a) {int64_t t;is >> t;a = ModInt< mod >(t);return (is);}static int get_mod() { return mod; }};constexpr int mod = 1000000007;using mint = ModInt< mod >;template< typename Mint >using FPS = FormalPowerSeries< Mint >;using fps = FPS<mint>;/*** @brief Coeff of Rational Function* @docs docs/coeff-of-rational-function.md*/template< template< typename > class FPS, typename Mint >Mint coeff_of_rational_function(FPS< Mint > P, FPS< Mint > Q, int64_t k) {// compute the coefficient [x^k] P/Q of rational power seriesMint ret = 0;if(P.size() >= Q.size()) {auto R = P / Q;P -= R * Q;P.shrink();if(k < (int) R.size()) ret += R[k];}if(P.empty()) return ret;P.resize((int) Q.size() - 1);auto sub = [&](const FPS< Mint > &as, bool odd) {FPS< Mint > bs((as.size() + !odd) / 2);for(int i = odd; i < (int) as.size(); i += 2) bs[i >> 1] = as[i];return bs;};while(k > 0) {auto Q2(Q);for(int i = 1; i < (int) Q2.size(); i += 2) Q2[i] = -Q2[i];P = sub(P * Q2, k & 1);Q = sub(Q * Q2, 0);k >>= 1;}return ret + P[0];}int main(){ios_base::sync_with_stdio(false);cin.tie(nullptr);ll n; in(n);fps f = {1};mint x = (mint)1 / (mint)6;fps g = {1,-x,-x,-x,-x,-x,-x};out(coeff_of_rational_function(f,g,n));}