#394027 (C++14) No.510 二次漸化式

提出ソース

結果

問題	No.510 二次漸化式
ユーザー	chocorusk
提出日時	2019-10-26 16:29:28
言語	C++14 (gcc 12.3.0 + boost 1.83.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

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	50 ms 5,376 KB
testcase_03	AC	50 ms 5,376 KB
testcase_04	AC	50 ms 5,376 KB
testcase_05	AC	50 ms 5,376 KB
testcase_06	AC	67 ms 6,528 KB
testcase_07	AC	68 ms 6,528 KB
testcase_08	AC	66 ms 6,656 KB
testcase_09	AC	66 ms 6,528 KB
testcase_10	AC	32 ms 5,376 KB
testcase_11	AC	32 ms 5,376 KB
testcase_12	AC	33 ms 5,376 KB
testcase_13	AC	32 ms 5,376 KB
testcase_14	AC	32 ms 5,376 KB
testcase_15	AC	32 ms 5,376 KB
testcase_16	AC	71 ms 32,256 KB
testcase_17	AC	72 ms 32,044 KB
testcase_18	AC	72 ms 32,128 KB
testcase_19	AC	73 ms 32,128 KB
testcase_20	AC	72 ms 32,128 KB
testcase_21	AC	72 ms 32,068 KB
testcase_22	AC	71 ms 32,052 KB
testcase_23	AC	109 ms 32,000 KB
testcase_24	AC	109 ms 32,128 KB
testcase_25	AC	109 ms 32,112 KB
testcase_26	AC	109 ms 32,044 KB
testcase_27	AC	107 ms 32,048 KB
testcase_28	AC	109 ms 32,128 KB
testcase_29	AC	109 ms 32,128 KB
testcase_30	AC	108 ms 32,128 KB
testcase_31	AC	111 ms 32,060 KB
testcase_32	AC	112 ms 32,096 KB
testcase_33	AC	118 ms 32,052 KB
testcase_34	AC	102 ms 32,128 KB
testcase_35	AC	91 ms 32,204 KB

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

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード