結果

問題 No.510 二次漸化式
ユーザー anta
提出日時 2018-04-06 19:19:59
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 101 ms / 3,000 ms
コード長 4,941 bytes
コンパイル時間 1,927 ms
コンパイル使用メモリ 178,288 KB
実行使用メモリ 35,968 KB
最終ジャッジ日時 2024-06-26 10:49:24
合計ジャッジ時間 6,158 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }
template<int MOD>
struct ModInt {
    static const int Mod = MOD;
    unsigned x;
    ModInt() : x(0) { }
    ModInt(signed sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
    ModInt(signed long long sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
    int get() const { return (int)x; }
    ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
    ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
    ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
    ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
};
typedef ModInt<1000000007> mint;
struct Matrix {
    typedef mint Num;
    static const int MaxN = 4;
    int hei, wid;
    Num v[MaxN][MaxN];
    Matrix() {}
    Matrix(int n, int m) : hei(n), wid(m) { memset(v, 0, sizeof(v)); }
    inline int height() const { return hei; }
    inline int width() const { return wid; }
    inline Num& at(int i, int j) { return v[i][j]; }
    inline const Num& at(int i, int j) const { return v[i][j]; }
    static Matrix identity(int n) {
        Matrix A(n, n);
        rep(i, n) A.at(i, i) = 1;
        return A;
    }
    inline static Matrix identity(const Matrix& A) { return identity(A.height()); }
    Matrix& operator*=(const Matrix& B) {
        int n = height(), m = B.width(), p = B.height();
        assert(p == width());
        const unsigned(*b)[MaxN] = reinterpret_cast<const unsigned(*)[MaxN]>(B.v);
        Num w[MaxN][MaxN];
        unsigned long long pp = (1ULL << 32) % mint::Mod;
        rep(i, n) {
            const unsigned *ai = reinterpret_cast<const unsigned*>(v[i]);
            rep(j, m) {
                unsigned x0 = 0; unsigned long long x1 = 0;
                rep(k, p) {
                    unsigned long long y = (unsigned long long)ai[k] * b[k][j];
                    unsigned long long t = x0 + y;
                    x1 += t >> 32;
                    x0 = t & 0xffffffff;
                }
                w[i][j].x = (x0 + x1 % mint::Mod * pp) % mint::Mod;
            }
        }
        memcpy(v, w, sizeof(v));
        wid = m;
        return *this;
    }
};
struct GetRangeSegmentTree {
    typedef Matrix Val;
    static Val combineVal(const Val &x, const Val &y) { return Matrix(x) *= y; }
    static void assignCombineVal(Val &x, const Val &y) { x *= y; }
    static Val identityVal() { return Matrix::identity(4); }
    vector<Val> nodes;
    int n;
    void init(int n_, const Val &v = Val()) { init(vector<Val>(n_, v)); }
    void init(const vector<Val> &u) {
        n = 1; while (n < (int)u.size()) n *= 2;
        nodes.resize(n, identityVal());
        nodes.insert(nodes.end(), u.begin(), u.end());
        nodes.resize(n * 2, identityVal());
        for (int i = n - 1; i > 0; -- i)
            nodes[i] = combineVal(nodes[i * 2], nodes[i * 2 + 1]);
    }
    Val get(int i) {
        return nodes[i + n];
    }
    Val getWhole() const {
        return nodes[1];
    }
    Val getRange(int l, int r) const {
        Val m = identityVal();
        int indices[64]; int k = 0;
        for (; l && l + (l&-l) <= r; l += l & -l)
            assignCombineVal(m, nodes[(n + l) / (l&-l)]);
        for (; l < r; r -= r & -r)
            indices[k ++] = (n + r) / (r&-r) - 1;
        while (-- k >= 0) assignCombineVal(m, nodes[indices[k]]);
        return m;
    }
    void set(int i, const Val &x) {
        i += n; nodes[i] = x;
        for (i >>= 1; i > 0; i >>= 1)
            nodes[i] = combineVal(nodes[i * 2], nodes[i * 2 + 1]);
    }
};
int main() {
    int N; int Q;
    while (~scanf("%d%d", &N, &Q)) {
        //b_{i+1}^2 = (y_i b_i + 1)^2 = y_i^2 b_i^2 + 2 y_i b_i + 1
        auto getMatrix = [](mint x, mint y) -> Matrix {
            Matrix A(4, 4);
            //1 -> 1
            A.at(0, 0) = 1;
            //b_{i+1}
            A.at(1, 1) = y;
            A.at(0, 1) = 1;
            //b_{i+1}^2
            A.at(2, 2) = y * y;
            A.at(1, 2) = y * 2;
            A.at(0, 2) = 1;
            //a_{i+1}
            A.at(3, 3) = 1;
            A.at(2, 3) = x;
            return A;
        };
        GetRangeSegmentTree segt;
        segt.init(N, getMatrix(0, 0));
        vector<mint> xs(N), ys(N);
        for (int ii = 0; ii < Q; ++ ii) {
            char ty[10];
            scanf("%s", ty);
            if (*ty == 'x' || *ty == 'y') {
                int i; int v;
                scanf("%d%d", &i, &v);
                (*ty == 'x' ? xs[i] : ys[i]) = v;
                segt.set(i, getMatrix(xs[i], ys[i]));
            } else if (*ty == 'a') {
                int i;
                scanf("%d", &i);
                auto A = segt.getRange(0, i);
                Matrix v(1, 4);
                v.at(0, 0) = 1;
                v.at(0, 1) = 1;
                v.at(0, 2) = 1;
                v.at(0, 3) = 1;
                v *= A;
                mint ans = v.at(0, 3);
                printf("%d\n", ans.get());
            } else abort();
        }
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0