結果

問題 No.1073 無限すごろく
コンテスト
ユーザー penta
提出日時 2020-06-12 22:59:44
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 8 ms / 2,000 ms
コード長 6,167 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,068 ms
コンパイル使用メモリ 199,172 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-24 05:44:06
合計ジャッジ時間 3,895 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using P = pair<int,int>;
template <class T> void chmin(T &a, const T &b) noexcept { if (b < a) a = b; }
template <class T> void chmax(T &a, const T &b) noexcept { if (a < b) a = b; }


template <ll Modulo>
struct modint {
private:
  static constexpr ll mod = Modulo;
public:
  ll x;
  modint(ll x=0):x((x%mod+mod)%mod){}
  modint operator-() const { return modint(-x);}
  modint& operator+=(const modint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  modint& operator-=(const modint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  modint& operator*=(const modint a) { (x *= a.x) %= mod; return *this;}
  modint operator+(const modint a) const { return modint(*this) += a;}
  modint operator-(const modint a) const { return modint(*this) -= a;}
  modint operator*(const modint a) const { return modint(*this) *= a;}
  modint pow(ll t) const {
    if (!t) return 1;
    modint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
  // for prime mod
  modint inv() const { return pow(mod-2);}
  modint& operator/=(const modint a) { return *this *= a.inv();}
  modint operator/(const modint a) const { return modint(*this) /= a;}
  bool operator==(const modint rhs) const { return x == rhs.x; }
  bool operator!=(const modint rhs) const { return x != rhs.x; }
  bool operator<(const modint &a) const{ return x<a.x;};
  static ll get_mod() { return mod; }
};

struct Garner {
private:
  vector<ll> r, m;
  ll extgcd(ll a, ll b, ll& x, ll& y) {
    for (ll u=y=1, v=x=0; a; ) {
      ll q = b / a;
      swap(x -= q*u, u);
      swap(y -= q*v, v);
      swap(b -= q*a, a);
    }
    return b;
  }
  inline ll mod_inv(ll a, ll mod) {
    ll x, y;
    extgcd(a, mod, x, y);
    return (mod + x % mod) % mod;
  }

public:
  void push(ll v, ll mod) {
    r.emplace_back(v);
    m.emplace_back(mod);
  }
  ll get(ll mod) {
    r.emplace_back(0);
    m.emplace_back(mod);
    vector<ll> coffs(r.size(),1), constants(r.size(),0);
    for (int i = 0; i < (int)r.size()-1; ++i) {
      // solve "coffs[i] * v + constants[i] = r[i] (mod m[i])"
      ll v = (r[i] - constants[i]) * mod_inv(coffs[i], m[i]) % m[i];
      if (v < 0) v += m[i];
      for (int j = i+1; j < (int)r.size(); ++j) {
        (constants[j] += coffs[j] * v) %= m[j];
        (coffs[j] *= m[i]) %= m[j];
      }
    } 
    return constants.back();
  }
};


template<typename ModInt> struct NTT {
private:
  using mi = ModInt;

  static mi primitive_root() {
    ll p = mi{}.get_mod();
    if (p == 167772161) return 3;
    else if (p == 469762049) return 3;
    else if (p == 1224736769) return 3;
    else if (p == 998244353) return 3;
    return 0;
  }
  unsigned bitreverse32(unsigned x) {
    x = ((x & 0x55555555) << 1) | ((x >> 1) & 0x55555555);
    x = ((x & 0x33333333) << 2) | ((x >> 2) & 0x33333333);
    x = ((x & 0x0F0F0F0F) << 4) | ((x >> 4) & 0x0F0F0F0F);
    x = (x << 24) | ((x & 0xFF00) << 8) | ((x >> 8) & 0xFF00) | (x >> 24);
    return x;
  }

public:
  void ntt(vector<mi> &A, const int k, bool inverse = false) {
    if (k == 0) return;
    for (int i = 1; i < (1<<k); ++i) { 
      int ind = bitreverse32(i) >> (32-k);
      if (ind > i) {
        std::swap(A[i], A[ind]);
      }  
    }
    for (int i = 1; i <= k; ++i) { //N = (1<<i)
      mi w = primitive_root().pow((mi(-1)/(1<<i)).x);
      if (inverse) w = mi(1) / w;
      for (int j = 0; j < (1<<(k-i)); ++j) { 
        mi base = 1;
        for (int l = 0; l < (1<<(i-1)); ++l) { //l = 0,1...N/2-1
          mi s = A[(1<<i)*j + l];
          mi t = A[(1<<i)*j + l + (1<<(i-1))] * base;
          A[(1<<i)*j + l] = s + t;
          A[(1<<i)*j + l + (1<<(i-1))] = s - t;
          base *= w;
        }
      }
    }
    if (inverse) {
      for (int i = 0; i < (1<<k); ++i) A[i] /= (1<<k);
    }
  }

  vector<ll> convolve(const vector<ll>& A, const vector<ll>& B){
    int siz = A.size() + B.size() - 1;
    int k = 0;
    while (siz >= (1<<k)) k++;
    vector<mi> CA(1<<k,0), CB(1<<k,0);
    for (int i = 0; i < (int)A.size(); ++i) CA[i] = A[i];
    for (int i = 0; i < (int)B.size(); ++i) CB[i] = B[i];
    ntt(CA, k, false);
    ntt(CB, k, false);
    vector<mi> CC(1<<k);
    for (int i = 0; i < (1<<k); ++i) {
      CC[i] = CA[i] * CB[i];
    }
    ntt(CC, k, true);
    vector<ll> C(siz);
    for (int i = 0; i < siz; ++i) C[i] = CC[i].x;
    return C;
  }
};

vector<ll> ntt_convolve(vector<ll> &A, vector<ll> &B, ll mod = 1224736769) {
  if (mod == 998244353) {
    NTT<modint<998244353> > ntt;
    return ntt.convolve(A,B);
  }
  NTT<modint<167772161> > ntt1;
  NTT<modint<469762049> > ntt2;
  NTT<modint<1224736769> > ntt3;
  vector<ll> C1 = ntt1.convolve(A,B);
  vector<ll> C2 = ntt2.convolve(A,B);
  vector<ll> C3 = ntt3.convolve(A,B);
  vector<ll> res(C1.size());
  for (int i = 0; i < (int)C1.size(); ++i) {
    Garner garner;
    garner.push(C1[i], 167772161);
    garner.push(C2[i], 469762049);
    garner.push(C3[i], 1224736769);
    res[i] = garner.get(mod);
  }
  return res;
}



ll coef_of_G(vector<ll> P, vector<ll> Q, ll n, const ll mod = 1000000007) {
  assert(P.size() + 1 == Q.size());
  while (n > 0) {
    vector<ll> NQ = Q;
    for (int i=1; i<(int)Q.size(); i+=2) { //Q(-z)
      NQ[i] *= -1;
      NQ[i] %= mod;
      if (NQ[i] < 0) NQ[i] += mod;
    }
    auto PNQ = ntt_convolve(P, NQ, mod); //P(z)Q(-z)
    if (n&1) {
      for (int i=0; i<(int)P.size(); ++i) P[i] = PNQ[2*i+1];
    }
    else {
      for (int i=0; i<(int)P.size(); ++i) P[i] = PNQ[2*i];
    }
    auto QNQ = ntt_convolve(Q, NQ, mod); //Q(z)Q(-z)
    for (int i=0; i<(int)Q.size(); ++i) Q[i] = QNQ[2*i];
    n /= 2;
  }
  return P[0];
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  ll n;
  cin >> n;
  using mint = modint<1000000007>;
  mint prob = mint(-1)/6;
  vector<ll> P = {1, 0, 0, 0, 0, 0};
  vector<ll> Q = {1, prob.x, prob.x, prob.x, prob.x, prob.x, prob.x};
  cout << coef_of_G(P, Q, n, 1000000007) << endl;
  return 0;
}
0