#655657 (C++17) No.1500 Super Knight

提出ソース

結果

問題	No.1500 Super Knight
ユーザー	cardano1016
提出日時	2021-05-08 19:01:36
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	3 ms / 2,000 ms
コード長	9,245 bytes
コンパイル時間	4,018 ms
コンパイル使用メモリ	189,776 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-09-17 00:48:29
合計ジャッジ時間	5,242 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	3 ms 6,944 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	3 ms 6,940 KB
testcase_08	AC	2 ms 6,944 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	2 ms 6,940 KB
testcase_12	AC	2 ms 6,940 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	2 ms 6,940 KB
testcase_15	AC	2 ms 6,944 KB
testcase_16	AC	2 ms 6,944 KB
testcase_17	AC	2 ms 6,940 KB
testcase_18	AC	2 ms 6,940 KB
testcase_19	AC	2 ms 6,940 KB
testcase_20	AC	2 ms 6,944 KB
testcase_21	AC	2 ms 6,944 KB
testcase_22	AC	2 ms 6,940 KB
testcase_23	AC	2 ms 6,940 KB
testcase_24	AC	2 ms 6,940 KB
testcase_25	AC	2 ms 6,944 KB
testcase_26	AC	2 ms 6,940 KB
testcase_27	AC	3 ms 6,940 KB
testcase_28	AC	2 ms 6,940 KB
testcase_29	AC	2 ms 6,944 KB
testcase_30	AC	3 ms 6,944 KB
testcase_31	AC	2 ms 6,940 KB
testcase_32	AC	2 ms 6,944 KB
testcase_33	AC	2 ms 6,944 KB
testcase_34	AC	2 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <assert.h>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <unordered_map>
#include <numeric>
#include <functional>
#include <atcoder/all>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=a;i<b;++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define _rrep(i,a) rrepi(i,a,0)
#define rrepi(i,a,b) for(int i=a-1;i>=b;--i)
#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using namespace atcoder;
using ll = long long;
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; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}

const ll INF = 1e18;
const ll MOD = 1000000007;
const ll MOD2 = 998244353;
const ll MOD3 = 1e6;
const ll EPS = 1e-10;
int sgn(const double a){
    return (a < -EPS ? -1 : (a > EPS ? +1 : 0));
}
typedef pair<int,int> pi;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> tri;
typedef pair<double,double> point;
typedef complex<double> Point;
const ll MAX = 105;
constexpr ll nx[4] = {-1,0,1,0};
constexpr ll ny[4] = {0,1,0,-1};

template<class T>
struct FormalPowerSeries : vector<T> {
    using vector<T>::vector;
    using vector<T>::operator=;
    using F = FormalPowerSeries;

    F operator-() const {
        F res(*this);
        for (auto &e : res) e = -e;
        return res;
    }
    F &operator*=(const T &g) {
        for (auto &e : *this) e *= g;
        return *this;
    }
    F &operator/=(const T &g) {
        assert(g != T(0));
        *this *= g.inv();
        return *this;
    }
    F &operator+=(const F &g) {
        int n = (*this).size(), m = g.size();
        rep(i, min(n, m)) (*this)[i] += g[i];
        return *this;
    }
    F &operator-=(const F &g) {
        int n = (*this).size(), m = g.size();
        rep(i, min(n, m)) (*this)[i] -= g[i];
        return *this;
    }
    F &operator<<=(const int d) {
        int n = (*this).size();
        (*this).insert((*this).begin(), d, 0);
        (*this).resize(n);
        return *this;
    }
    F &operator>>=(const int d) {
        int n = (*this).size();
        (*this).erase((*this).begin(), (*this).begin() + min(n, d));
        (*this).resize(n);
        return *this;
    }
    F inv(int d = -1) const {
        int n = (*this).size();
        assert(n != 0 && (*this)[0] != 0);
        if (d == -1) d = n;
        assert(d > 0);
        F res{(*this)[0].inv()};
        while (res.size() < d) {
            int m = size(res);
            F f(begin(*this), begin(*this) + min(n, 2*m));
            F r(res);
            f.resize(2*m), internal::butterfly(f);
            r.resize(2*m), internal::butterfly(r);
            rep(i, 2*m) f[i] *= r[i];
            internal::butterfly_inv(f);
            f.erase(f.begin(), f.begin() + m);
            f.resize(2*m), internal::butterfly(f);
            rep(i, 2*m) f[i] *= r[i];
            internal::butterfly_inv(f);
            T iz = T(2*m).inv(); iz *= -iz;
            rep(i, m) f[i] *= iz;
            res.insert(res.end(), f.begin(), f.begin() + m);
        }
        return {res.begin(), res.begin() + d};
    }

    //fast: FMT-friendly modulus only
    /*
    F &operator*=(const F &g) {
        int n = (*this).size();
        *this = convolution(*this, g);
        (*this).resize(n);
        return *this;
    }
    F &operator/=(const F &g) {
        int n = (*this).size();
        *this = convolution(*this, g.inv(n));
        (*this).resize(n);
        return *this;
    }*/

    //naive
    F &operator*=(const F &g) {
        int n = (*this).size(), m = g.size();
        rrep(i, n) {
            (*this)[i] *= g[0];
            rep(j, 1, min(i+1, m)) (*this)[i] += (*this)[i-j] * g[j];
        }
        return *this;
    }
    F &operator/=(const F &g) {
        assert(g[0] != T(0));
        T ig0 = g[0].inv();
        int n = (*this).size(), m = g.size();
        rep(i, n) {
            rep(j, 1, min(i+1, m)) (*this)[i] -= (*this)[i-j] * g[j];
            (*this)[i] *= ig0;
        }
        return *this;
    }

    //sparse
    F &operator*=(vector<pair<int, T>> g) {
        int n = (*this).size();
        auto [d, c] = g.front();
        if (d == 0) g.erase(g.begin());
        else c = 0;
        rrep(i, n) {
            (*this)[i] *= c;
            for (auto &[j, b] : g) {
                if (j > i) break;
                (*this)[i] += (*this)[i-j] * b;
            }
        }
        return *this;
    }
    F &operator/=(vector<pair<int, T>> g) {
        int n = (*this).size();
        auto [d, c] = g.front();
        assert(d == 0 && c != T(0));
        T ic = c.inv();
        g.erase(g.begin());
        rep(i, n) {
            for (auto &[j, b] : g) {
                if (j > i) break;
                (*this)[i] -= (*this)[i-j] * b;
            }
            (*this)[i] *= ic;
        }
        return *this;
    }

    //multiply and divide (1 + cz^d)
    void multiply(const int d, const T c) { 
        int n = (*this).size();
        if (c == T(1)) rrep(i, n-d) (*this)[i+d] += (*this)[i];
        else if (c == T(-1)) rrep(i, n-d) (*this)[i+d] -= (*this)[i];
        else rrep(i, n-d) (*this)[i+d] += (*this)[i] * c;
    }
    void divide(const int d, const T c) {
        int n = (*this).size();
        if (c == T(1)) rep(i, n-d) (*this)[i+d] -= (*this)[i];
        else if (c == T(-1)) rep(i, n-d) (*this)[i+d] += (*this)[i];
        else rep(i, n-d) (*this)[i+d] -= (*this)[i] * c;
    }

    T eval(const T &a) const {
        T x(1), res(0);
        for (auto e : *this) res += e * x, x *= a;
        return res;
    }

    F operator*(const T &g) const { return F(*this) *= g; }
    F operator/(const T &g) const { return F(*this) /= g; }
    F operator+(const F &g) const { return F(*this) += g; }
    F operator-(const F &g) const { return F(*this) -= g; }
    F operator<<(const int d) const { return F(*this) <<= d; }
    F operator>>(const int d) const { return F(*this) >>= d; }
    F operator*(const F &g) const { return F(*this) *= g; }
    F operator/(const F &g) const { return F(*this) /= g; }
    F operator*(vector<pair<int, T>> g) const { return F(*this) *= g; }
    F operator/(vector<pair<int, T>> g) const { return F(*this) /= g; }
};

using mint = modint1000000007;
using fps = FormalPowerSeries<mint>;
using sfps = vector<pair<int,mint>>;

// p/qの有理式で表される母関数のn番目(0-indexed)
ll recur(ll n,fps p,fps q){
    if (n == 0) return p[0].val();
    ll s = q.size();
    p.resize(2*s);
    q.resize(2*s);
    fps mq = q;
    rep(i,s){
        if (i%2 == 1){
            mq[i] = -mq[i];
        }
    }
    ll res;
    fps qmq = q*mq,pmq = p*mq,v(s);
    rep(i,s){
        v[i] = qmq[2*i];
    }
    if (n%2 == 0){
        fps e(s,0);
        rep(i,s){
            e[i] = pmq[2*i];
        }
        res = recur(n/2,e,v);
    }
    else{
        fps o(s,0);
        rep(i,s){
            o[i] = pmq[2*i+1];
        }
        res = recur((n-1)/2,o,v);
    }
    return res;
}

inline ll Mod(ll a,ll m){
    return (a%m + m)%m;
}

ll extGCD(ll a,ll b,ll &p,ll &q){
    if (b == 0){
        p = 1;q = 0;return a;
    }
    ll d = extGCD(b,a%b,q,p);
    q -= a/b*p;
    return d;
}

ll mod_inv(ll a,ll m){
    ll x,y;
    extGCD(a,m,x,y);
    return Mod(x,m);
}

template<class F>
F Berlekamp_Massey(F s){
    using T = typename F::value_type;
    ll n = s.size();
    F c{-1},c2{0};
    T r2 = 1;
    ll i2 = -1;
    rep(i,n){
        ll d = c.size();
        T r = 0;
        rep(j,d){
            r += c[j]*s[i-j];
        }
        if (r == 0){
            continue;
        }
        T coef = -r/r2;
        ll d2 = c2.size();
        if (d-i >= d2-i2){
            rep(j,d2){
                c[j+i-i2] += c2[j]*coef;
            }
        }
        else{
            auto tmp = c;
            c.resize(d2+i-i2);
            rep(j,d2){
                c[j+i-i2] += c2[j]*coef;
            }
            c2 = move(tmp);
            i2 = i,r2 = r;
        }
    }
    return c;
}

template<class F>
ll get(ll k,F s){
    auto a = Berlekamp_Massey(s);
    fps q(a.begin()+1,a.end()),t(s.begin(),s.end());
    q.insert(q.begin(),-1);
    ll n = t.size();
    fps p = t*q;
    return recur(k,p,q);
}

int main(){
    vector<mint> s{0,1,12,65,172,297,456,649,876,1137,1432,1761,2124,2521,2952,3417};
    ll n;
    cin >> n;
    PRINT(get(n+1,s));
}

yukicoder

結果

テストケース

ソースコード