結果

問題 No.578 3 x N グリッド上のサイクルのサイズ(easy)
ユーザー yosupot
提出日時 2017-10-13 23:21:29
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 12,468 bytes
コンパイル時間 2,110 ms
コンパイル使用メモリ 133,796 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-17 11:48:50
合計ジャッジ時間 3,161 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <numeric>
#include <random>
#include <vector>
#include <array>
#include <bitset>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;

struct rng {
    struct A {
        int n;
        const bool operator!=(A r) { return n != r.n; }
        A& operator++() { n++; return *this; }
        int operator*() { return n; }
    };
    int l, r;
    rng(int r) : l(0), r(max(0, r)) {}
    rng(int l, int r) : l(l), r(max(l, r)) {}
    A begin() { return A{l}; }
    A end() { return A{r}; }
};

//bit op
int bsr(uint x) { return 31 - __builtin_clz(x); }
int bsr(ull x) { return 63 - __builtin_clzll(x); }
int bsf(uint x) { return __builtin_ctz(x); }
int bsf(ull x) { return __builtin_ctzll(x); }


template<class T>
T pow(T x, ll n, T r) {
    while (n) {
        if (n & 1) r *= x;
        x *= x;
        n >>= 1;
    }
    return r;
}
template<class T> T pow(T x, ll n) { return pow(x, n, T(1)); }

template<uint MD>
struct ModInt {
    uint v;
    ModInt() : v{0} {}
    ModInt(ll v) : v{normS(v%MD+MD)} {}
    explicit operator bool() const {return v != 0;}
    static uint normS(uint x) {return (x<MD)?x:x-MD;};
    static ModInt make(uint x) {ModInt m; m.v = x; return m;}
    static ModInt inv(const ModInt &x) {return pow(ModInt(x), MD-2);} 
    ModInt operator+(const ModInt &r) const {return make(normS(v+r.v));}
    ModInt operator-(const ModInt &r) const {return make(normS(v+MD-r.v));}
    ModInt operator*(const ModInt &r) const {return make(ull(v)*r.v%MD);}
    ModInt operator/(const ModInt &r) const {return *this*inv(r);}
    ModInt& operator+=(const ModInt &r) {return *this=*this+r;}
    ModInt& operator-=(const ModInt &r) {return *this=*this-r;}
    ModInt& operator*=(const ModInt &r) {return *this=*this*r;}
    ModInt& operator/=(const ModInt &r) {return *this=*this/r;}
};
template<uint MD> string to_string(ModInt<MD> m) {return to_string(m.v);}
using Mint = ModInt<TEN(9)+7>;

using R = double;
struct Pc {
    R x, y;
    Pc() : x(0), y(0) {}
    Pc(R x, R y) : x(x), y(y) {}
    Pc operator+(const Pc &r) const {return Pc(x+r.x, y+r.y);}
    Pc operator-(const Pc &r) const {return Pc(x-r.x, y-r.y);}
    Pc operator*(const Pc &r) const {return Pc(x*r.x-y*r.y, x*r.y+y*r.x);}
    Pc operator*(const R &r) const {return Pc(x*r, y*r);}
    Pc& operator+=(const Pc &r) {return *this=*this+r;}
    Pc& operator-=(const Pc &r) {return *this=*this-r;}
    Pc& operator*=(const Pc &r) {return *this=*this*r;}   
    Pc& operator*=(const R &r) {return *this=*this*r;}
    static Pc polar(R r, R th) {return Pc(cos(th)*r, sin(th)*r);}
};
const R PI = 4*atan(R(1));

void fft(bool type, V<Pc> &c) {
    static V<Pc> buf[30];
    int N = int(c.size());
    int s = bsr(uint(N));
    assert(1<<s == N);
    if (!buf[s].size()) {
        buf[s] = V<Pc>(N);
        for (int i = 0; i < N; i++) {
            buf[s][i] = Pc::polar(1, i*2*PI/N);
        }
    }
    V<Pc> a = c, b(N);
    for (int i = 1; i <= s; i++) {
        int W = 1<<(s-i); //変更後の幅W
        for (int y = 0; y < N/2; y += W) {
            Pc now = buf[s][y]; if (type) now.y *= -1;
            for (int x = 0; x < W; x++) {
                auto l =       a[y<<1 | x];
                auto r = now * a[y<<1 | x | W];
                b[y | x]        = l+r;
                b[y | x | N>>1] = l-r;
            }
        }
        swap(a, b);            
    }
    c = a;
}

template<class Mint>
V<Mint> multiply(V<Mint> x, V<Mint> y) {
    constexpr int B = 3, SHIFT = 10;
    int S = x.size()+y.size()-1;
    int N = 2<<bsr(uint(S-1));
    V<Pc> a[B], b[B];
    for (int fe = 0; fe < B; fe++) {
        a[fe] = V<Pc>(N);
        b[fe] = V<Pc>(N);
        V<Pc> c(N);
        for (int i = 0; i < int(x.size()); i++) {
            c[i].x = (x[i].v >> (fe*SHIFT)) & ((1<<SHIFT)-1);
        }
        for (int i = 0; i < int(y.size()); i++) {
            c[i].y = (y[i].v >> (fe*SHIFT)) & ((1<<SHIFT)-1);
        }
        fft(false, c);
        for (int i = 0; i < N; i++) {
            c[i] *= 0.5;
        }
        for (int i = 0; i < N; i++) {
            int j = (N-i)%N;
            a[fe][i] = Pc(c[i].x+c[j].x, c[i].y-c[j].y);
            b[fe][i] = Pc(c[i].y+c[j].y, -c[i].x+c[j].x);
        }
    }
    V<Mint> z(S);
    V<Pc> c[B];
    for (int fe = 0; fe < B; fe++) {
        c[fe] = V<Pc>(N);
    }
    for (int af = 0; af < B; af++) {
        for (int bf = 0; bf < B; bf++) {
            int cf = (af+bf)%B;
            for (int i = 0; i < N; i++) {
                if (af+bf<B) {
                    c[cf][i] += a[af][i]*b[bf][i];
                } else {
                    c[cf][i] += a[af][i]*b[bf][i]*Pc(0, 1);
                }
            }
        }
    }
    for (int fe = 0; fe < B; fe++) {
        fft(true, c[fe]);
    }
    Mint base = 1;
    for (int fe = 0; fe < 2*B-1; fe++) {
        for (int i = 0; i < S; i++) {
            if (fe < B) {
                c[fe][i].x *= 1.0/N;
                z[i] += Mint(ll(round(c[fe][i].x)))*base;
            } else {       
                c[fe-B][i].y *= 1.0/N;
                z[i] += Mint(ll(round(c[fe-B][i].y)))*base;
            }
        }
        base *= 1<<SHIFT;
    }
    return z;
}

template<class D>
struct Poly {
    V<D> v;
    int size() const {return int(v.size());}
    Poly(int N = 0) : v(V<D>(N)) {}
    Poly(const V<D> &v) : v(v) {shrink();}
    Poly& shrink() {while (v.size() && !v.back()) v.pop_back(); return *this;}
    D freq(int p) const { return (p < size()) ? v[p] : D(0); }

    Poly operator+(const Poly &r) const {
        int N = size(), M = r.size();
        V<D> res(max(N, M));
        for (int i = 0; i < max(N, M); i++) res[i] = freq(i)+r.freq(i);
        return Poly(res);
    }
    Poly operator-(const Poly &r) const {
        int N = size(), M = r.size();
        V<D> res(max(N, M));
        for (int i = 0; i < max(N, M); i++) res[i] = freq(i)-r.freq(i);
        return Poly(res);
    }
    Poly operator*(const Poly &r) const {
        int N = size(), M = r.size();
        if (min(N, M) == 0) return Poly();
        assert(N+M-1 >= 0);
        V<D> res = multiply(v, r.v);
        return Poly(res);
    }
    Poly operator*(const D &r) const {
        V<D> res(size());
        for (int i = 0; i < size(); i++) res[i] = v[i]*r;
        return Poly(res);
    }
    Poly& operator+=(const Poly &r) {return *this = *this+r;}
    Poly& operator-=(const Poly &r) {return *this = *this-r;}
    Poly& operator*=(const Poly &r) {return *this = *this*r;}
    Poly& operator*=(const D &r) {return *this = *this*r;}

    Poly operator<<(const int n) const {
        assert(n >= 0);
        V<D> res(size()+n);
        for (int i = 0; i < size(); i++) {
            res[i+n] = v[i];
        }
        return Poly(res);
    }
    Poly operator>>(const int n) const {
        assert(n >= 0);
        if (size() <= n) return Poly();
        V<D> res(size()-n);
        for (int i = n; i < size(); i++) {
            res[i-n] = v[i];
        }
        return Poly(res);
    }

    // x % y
    Poly rem(const Poly &y) const {
        return *this - y * div(y);
    }
    Poly rem_inv(const Poly &y, const Poly &ny, int B) const {
        return *this - y * div_inv(ny, B);
    }
    Poly div(const Poly &y) const {
        int B = max(size(), y.size());
        return div_inv(y.inv(B), B);
    }
    Poly div_inv(const Poly &ny, int B) const {
        return (*this*ny)>>(B-1);
    }
    // this * this.inv() = x^n + r(x) (size())
    Poly strip(int n) const {
        V<D> res = v;
        res.resize(min(n, size()));
        return Poly(res);
    }
    Poly rev(int n = -1) const {
        V<D> res = v;
        if (n != -1) res.resize(n);
        reverse(begin(res), end(res));
        return Poly(res);
    }
    // f * f.inv() = x^B + r(x) (B >= n)
    Poly inv(int n) const {
        int N = size();
        assert(N >= 1);
        assert(n >= N-1);
        Poly c = rev();
        Poly d = Poly(V<D>({D(1)/c.freq(0)}));
        int i;
        for (i = 1; i+N-2 < n; i *= 2) {
            auto u = V<D>({2});
            d = (d * (Poly(V<D>{2})-c*d)).strip(2*i);
        }
        return d.rev(n+1-N);
    }
};
template<class D>
string to_string(const Poly<D> &p) {
    if (p.size() == 0) return "0";
    string s = "";
    for (int i = 0; i < p.size(); i++) {
        if (p.v[i]) {
            s += to_string(p.v[i])+"x^"+to_string(i);
            if (i != p.size()-1) s += "+";
        }
    }
    return s;
}
// x^n % mod
template<class D>
Poly<D> nth_mod(ll n, const Poly<D> &mod) {
    int B = mod.size() * 2 - 1;
    Poly<D> mod_inv = mod.inv(B);
    Poly<D> p = V<D>{Mint(1)};
    int m = (!n) ? -1 : bsr(ull(n));
    for (int i = m; i >= 0; i--) {
        if (n & (1LL<<i)) {
            // += 1
            p = (p<<1).rem_inv(mod, mod_inv, B);
        }
        if (i) {
            // *= 2
            p = (p*p).rem_inv(mod, mod_inv, B);
        }
    }
    return p;
}
template<class D>
Poly<D> berlekamp_massey(const V<D> &s) {
    int N = int(s.size());
    V<D> b = {D(-1)}, c = {D(-1)};
    D y = D(1);
    for (int ed = 1; ed <= N; ed++) {
        int L = int(c.size()), M = int(b.size());
        D x = 0;
        for (int i = 0; i < L; i++) {
            x += c[i]*s[ed-L+i];
        }
        b.push_back(0); M++;
        if (!x) {
            continue;
        }
        D freq = x/y;
        if (L < M) {
            //use b
            auto tmp = c;
            c.insert(begin(c), M-L, D(0));
            for (int i = 0; i < M; i++) {
                c[M-1-i] -= freq*b[M-1-i];
            }
            b = tmp;
            y = x;
        } else {
            //use c
            for (int i = 0; i < M; i++) {
                c[L-1-i] -= freq*b[M-1-i];
            }
        }
    }
    return Poly<D>(c);
}

using Pol = Poly<Mint>;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(20);
    V<Mint> po = {
        0,
        32,
        316,
        2292,
        14422,
        84744,
        479004,
        2638328,
        14258574,
        75940592,
        399782668,
        84795558,
        786749020,
        442043859,
        352536615,
        76576421,
        744912747,
        420315017,
        25759333,
        562730793,
        424899366,
        153177921,
        250747498,
        306910436,
        324829483,
        572545341,
        104022619,
        226237183,
        421453002,
        754280938,
        291624319,
        60437277,
        297658752,
        677142927,
        63550828,
        801541292,
        683008492,
        650348,
        519624175,
        715484025,
        724658778,
        152363657,
        280344328,
        892278238,
        206785631,
        227202296,
        788486407,
        392284243,
        927772200,
        781378846,
        881515964,
        905982211,
        674841192,
        139044658,
        711210295,
        384364637,
        137653614,
        441363040,
        812818651,
        929556368,
        494420762,
        802527485,
        700803632,
        461521718,
        152786116,
        688977792,
        48724029,
        642700933,
        15567410,
        246397043,
        859581827,
        685250826,
        120226158,
        551687712,
        987163282,
        422276494,
        570671107,
        813070470,
        429968009,
        849487586,
        453150672,
        606112895,
        921636591,
        961537190,
        68995663,
        873642098,
        377371441,
        101407285,
        187434129,
        180415383,
        920712750,
        544594592,
        402649575,
        549811430,
        619506771,
        426917748,
        274013175,
        615469131,
        800944525,
        925880089,
    };

    auto pol = Pol(po);

    auto v = berlekamp_massey(po);

//    cout << to_string(v) << endl;

    ll x;
    cin >> x;
    auto z = nth_mod(x, v);
    Mint sm = 0;
    for (int i: rng(int(v.size()))) {
        sm += po[i] * z.freq(i);
    }
//    cout << to_string(z) << endl;
    cout << sm.v << endl;
    return 0;
}
0