結果

問題 No.510 二次漸化式
コンテスト
ユーザー vjudge1
提出日時 2025-02-24 16:44:42
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 383 ms / 3,000 ms
コード長 1,465 bytes
コンパイル時間 3,791 ms
コンパイル使用メモリ 276,384 KB
実行使用メモリ 55,156 KB
最終ジャッジ日時 2025-02-24 16:44:57
合計ジャッジ時間 13,519 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005,mod=1e9+7;
int n,q,x[N],y[N];string op;
struct matrix
{
	int c[4][4];
	matrix(){memset(c,0,sizeof(c));}
	matrix operator*(const matrix &p)const
	{
		matrix q;
		for(int i=0;i<4;i++)for(int j=0;j<4;j++)for(int k=0;k<4;k++)(q.c[i][j]+=c[i][k]*p.c[k][j])%=mod;
		return q;
	}
}sta,res,zh[N<<2];
matrix getmat(int x,int y)
{
	matrix z;
	z.c[0][0]=z.c[3][1]=z.c[3][2]=z.c[3][3]=1;
	z.c[1][0]=x;z.c[1][1]=y*y%mod;
	z.c[2][1]=2*y%mod;z.c[2][2]=y;
	return z;
}
void update(int u,int l,int r,int p,matrix w)
{
	if(p<l||p>r)return;
	if(l==r){zh[u]=w;return;}
	int mid=l+r>>1;
	update(u<<1,l,mid,p,w);
	update(u<<1|1,mid+1,r,p,w);
	zh[u]=zh[u<<1]*zh[u<<1|1];
}
matrix query(int u,int l,int r,int L,int R)
{
	if(r<L||l>R)
	{
		matrix I;
		for(int i=0;i<4;i++)I.c[i][i]=1;
		return I;
	}
	if(L<=l&&r<=R)return zh[u];
	int mid=l+r>>1;
	return query(u<<1,l,mid,L,R)*query(u<<1|1,mid+1,r,L,R);
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i=0;i<4;i++)sta.c[0][i]=1;
	for(int i=1;i<=n;i++)update(1,1,n,i,getmat(0,0));
	for(int i=1,p,v;i<=q;i++)
	{
		cin>>op>>p;
		if(op=="x")
		{
			cin>>v;
			update(1,1,n,p+1,getmat(v,y[p]));
			x[p]=v;
		}
		if(op=="y")
		{
			cin>>v;
			update(1,1,n,p+1,getmat(x[p],v));
			y[p]=v;
		}
		if(op=="a")
		{
			if(p==0)cout<<"1\n";
			else
			{
				res=sta*query(1,1,n,1,p);
				cout<<res.c[0][0]<<'\n';
			}
		}
	}
}
0