結果

問題 No.510 二次漸化式
コンテスト
ユーザー 小夫
提出日時 2025-02-28 22:47:04
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 169 ms / 3,000 ms
コード長 2,426 bytes
コンパイル時間 1,640 ms
コンパイル使用メモリ 176,672 KB
実行使用メモリ 33,824 KB
最終ジャッジ日時 2025-02-28 22:47:11
合計ジャッジ時間 6,024 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:103:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  103 |                 scanf(" %c",&op);
      |                 ~~~~~^~~~~~~~~~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<48||ch>57){if(ch=='-')f=-1;ch=getchar();}
	while(ch>=48&&ch<=57)x=(x<<1)+(x<<3)+(ch&15),ch=getchar();
	return x*f;
}
inline void write(int x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+48);
	return;
}
inline void openfile()
{
	freopen("16.in","r",stdin);
	freopen("generator.out","w",stdout);
}
constexpr int M=1e5+4,mod=1e9+7;
int X[M],Y[M];
struct Matrix
{
    int a[5][5];
    Matrix(){}
    inline void clear(){memset(a,0,sizeof a);}
    inline void init(int id)
	{
		a[1][1]=1,a[2][2]=Y[id],a[2][3]=2*Y[id]%mod;
		a[3][1]=X[id],a[3][3]=1ll*Y[id]*Y[id]%mod;
		a[4][2]=1,a[4][3]=1,a[4][4]=1;
		return;
	}
    inline Matrix operator*(const Matrix&b)const
	{
        Matrix res;
		res.clear();
        for(int k=1;k<=4;++k)
            for(int i=1;i<=4;++i)
                for(int j=1;j<=4;++j)
                    res.a[i][j]=(res.a[i][j]+1ll*a[i][k]*b.a[k][j]%mod)%mod;
        return res;
    }
    inline int value()
    {
    	int res=0;
    	for(int i=1;i<=4;++i)res=(res+a[i][1])%mod;
    	return res;
	}
};
struct SegmentTree
{
	#define lson rt<<1
	#define rson rt<<1|1
	struct node{int l,r;Matrix vl;}tr[M<<2];
	inline void update(int rt){tr[rt].vl=tr[lson].vl*tr[rson].vl;return;}
	inline void build(int rt,int l,int r)
	{
		tr[rt].l=l,tr[rt].r=r;
		if(l==r){tr[rt].vl.init(l);return;}
		int mid=l+r>>1;
		build(lson,l,mid);
		build(rson,mid+1,r);
		update(rt);
		return;
	}
	inline void modify(int rt,int pos)
	{
		int l=tr[rt].l,r=tr[rt].r;
		if(l==r){tr[rt].vl.init(l);return;}
		int mid=l+r>>1;
		if(pos<=mid)modify(lson,pos);
		if(pos>mid)modify(rson,pos);
		update(rt);
		return;
	}
	inline Matrix query(int rt,int posl,int posr)
	{
		int l=tr[rt].l,r=tr[rt].r;
		if(posl<=l&&r<=posr)return tr[rt].vl;
		Matrix res;
		res.clear();
		for(int i=1;i<=4;++i)res.a[i][i]=1;
		int mid=l+r>>1;
		if(posl<=mid)res=res*query(lson,posl,posr);
		if(posr>mid)res=res*query(rson,posl,posr);
		return res;
	}
	#undef lson
	#undef rson
}T;
int main()
{
	//openfile();
	int n=read()+1,q=read();
	T.build(1,1,n);
	for(int i=1;i<=q;++i)
	{
		char op;
		scanf(" %c",&op);
		int id=read();
        if(op=='x')X[id+1]=read(),T.modify(1,id+1);
        if(op=='y')Y[id+1]=read(),T.modify(1,id+1);
		if(op=='a')
		{
			auto ans=T.query(1,1,id);
	        write(ans.value()),puts("");
		}
	}
	return 0;
}
0