結果
問題 | No.510 二次漸化式 |
ユーザー |
![]() |
提出日時 | 2019-10-26 16:29:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 118 ms / 3,000 ms |
コード長 | 4,779 bytes |
コンパイル時間 | 1,287 ms |
コンパイル使用メモリ | 118,064 KB |
実行使用メモリ | 32,256 KB |
最終ジャッジ日時 | 2024-09-14 12:30:47 |
合計ジャッジ時間 | 6,429 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 34 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, int> P; template<int MOD> struct ModInt{ int x; ModInt(): x(0){} ModInt(ll 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.inv(); 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 pow(ll n) const{ ModInt ret(1), p(x); while(n){ if(n&1) ret*=p; p*=p; n>>=1; } return ret; } ModInt inv() const{ return pow(MOD-2); } }; const int MOD=1e9+7; using mint=ModInt<MOD>; template<typename T, size_t size> struct Matrix{ using arr=array<T, size>; array<arr, size> a; Matrix(){} Matrix(array<arr, size> a):a(a){} inline const arr &operator[](size_t k) const{ return a[k]; } inline arr &operator[](size_t k){ return a[k]; } static Matrix I(){ Matrix mat; for(int i=0; i<size; i++) mat[i][i]=1; return mat; } Matrix &operator+=(const Matrix &b){ for(int i=0; i<size; i++){ for(int j=0; j<size; j++){ (*this)[i][j]+=b[i][j]; } } return (*this); } Matrix &operator-=(const Matrix &b){ for(int i=0; i<size; i++){ for(int j=0; j<size; j++){ (*this)[i][j]-=b[i][j]; } } return (*this); } Matrix &operator*=(const Matrix &b){ array<arr, size> c; for(int i=0; i<size; i++){ for(int j=0; j<size; j++){ for(int k=0; k<size; k++){ c[i][j]+=(*this)[i][k]*b[k][j]; } } } for(int i=0; i<size; i++) for(int j=0; j<size; j++) (*this)[i][j]=c[i][j]; return (*this); } Matrix operator+(const Matrix &b) const{ return (Matrix(*this)+=b); } Matrix operator-(const Matrix &b) const{ return (Matrix(*this)-=b); } Matrix operator*(const Matrix &b) const{ Matrix c; for(int i=0; i<size; i++){ for(int j=0; j<size; j++){ for(int k=0; k<size; k++){ c[i][j]+=(*this)[i][k]*b[k][j]; } } } return c; } Matrix pow(ll k) const{ Matrix ap(a), ret=I(); while(k){ if(k&1) ret*=ap; ap*=ap; k>>=1; } return ret; } }; template<typename Monoid> struct SegmentTree{ using F=function<Monoid(Monoid, Monoid)>; int sz; vector<Monoid> seg; const F f; const Monoid e; SegmentTree(int n, const F f, const Monoid &e): f(f), e(e){ sz=1; while(sz<n) sz<<=1; seg.resize(2*sz, e); } SegmentTree(int n, const F f, const Monoid &e, vector<Monoid> v): f(f), e(e){ sz=1; while(sz<n) sz<<=1; seg.resize(2*sz, e); for(int i=0; i<n; i++) seg[i+sz]=v[i]; for(int i=sz-1; i>=1; i--){ seg[i]=f(seg[2*i], seg[2*i+1]); } } void update(int k, const Monoid &x){ k+=sz; seg[k]=x; while(k>1){ k>>=1; seg[k]=f(seg[2*k], seg[2*k+1]); } } Monoid query(int a, int b){ a+=sz, b+=sz; Monoid ret=e; for(;a<b; a>>=1, b>>=1){ if(b&1) ret=f(seg[--b], ret); if(a&1) ret=f(ret, seg[a++]); } return ret; } Monoid operator[](const int &k) const{ return seg[k+sz]; } }; int main() { using Mat=Matrix<mint, 4>; Mat id; id[0][0]=id[1][3]=id[2][3]=id[3][3]=1; int n; cin>>n; vector<Mat> v(n, id); SegmentTree<Mat> seg(n, [](Mat a, Mat b){ return b*a;}, Mat::I(), v); int q; cin>>q; for(int i=0; i<q; i++){ char c; cin>>c; if(c=='x'){ int p; mint val; cin>>p>>val.x; v[p][0][1]=val; seg.update(p, v[p]); }else if(c=='y'){ int p; mint val; cin>>p>>val.x; v[p][1][1]=val*val, v[p][1][2]=val*mint(2), v[p][2][2]=val; seg.update(p, v[p]); }else{ int p; cin>>p; Mat mat=seg.query(0, p); cout<<(mat[0][0]+mat[0][1]+mat[0][2]+mat[0][3]).x<<endl; } } return 0; }