結果

問題 No.510 二次漸化式
ユーザー vjudge1
提出日時 2025-02-26 20:59:39
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 147 ms / 3,000 ms
コード長 1,803 bytes
コンパイル時間 2,038 ms
コンパイル使用メモリ 169,828 KB
実行使用メモリ 61,028 KB
最終ジャッジ日時 2025-02-26 20:59:47
合計ジャッジ時間 7,368 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:63:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   63 |         scanf("%lld%lld",&n,&q);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
main.cpp:68:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   68 |                 scanf(" %c%lld",&op,&x);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~
main.cpp:70:34: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   70 |                 if(op=='x') scanf("%lld",&y),T.update(1,x,y,0);
      |                             ~~~~~^~~~~~~~~~~
main.cpp:71:39: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   71 |                 else if(op=='y') scanf("%lld",&y),T.update(1,x,y,1);
      |                                  ~~~~~^~~~~~~~~~~

ソースコード

diff # 

#include<bits/stdc++.h>
#define FL(i,a,b) for(ll i=(a);i<=(b);i++)
#define FR(i,a,b) for(ll i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const ll MAXN = 1e5 + 10;
const ll mod = 1e9 + 7;
ll n,q;
struct Matrix{
	ll a[5][5];
	void init(){
		memset(a,0,sizeof(a));
	}
};
Matrix operator*(const Matrix &a,const Matrix &b){
	Matrix res;
	res.init();
	FL(k,1,4)
		FL(i,1,4)
			FL(j,1,4)
				res.a[i][j]=(res.a[i][j]+a.a[i][k]*b.a[k][j]%mod)%mod;
	return res;
} 
struct Segment_Tree{
	#define ls (x<<1)
	#define rs (x<<1|1)
	struct node{
		ll l,r;
		Matrix sum;
	}t[MAXN<<2];
	void build(ll x,ll l,ll r){
		t[x].l=l,t[x].r=r;
		if(l==r){
			t[x].sum.init();
			t[x].sum.a[1][1]=t[x].sum.a[4][2]=t[x].sum.a[4][3]=t[x].sum.a[4][4]=1;
			return ;
		}
		ll mid=(l+r)>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
		t[x].sum=t[ls].sum*t[rs].sum;
	}
	void update(ll x,ll p,ll k,bool fg){
		if(t[x].l==t[x].r){
			if(fg) t[x].sum.a[2][2]=k,t[x].sum.a[2][3]=2*k%mod,t[x].sum.a[3][3]=k*k%mod;
			else t[x].sum.a[3][1]=k;
			return ;
		}
		ll mid=(t[x].l+t[x].r)>>1;
		if(p<=mid) update(ls,p,k,fg);
		else update(rs,p,k,fg);
		t[x].sum=t[ls].sum*t[rs].sum;
	}
	Matrix query(ll x,ll l,ll r){
		if(l<=t[x].l&&t[x].r<=r) return t[x].sum;
		ll mid=(t[x].l+t[x].r)>>1;
		if(r<=mid) return query(ls,l,r);
		else if(l>mid) return query(rs,l,r);
		else return query(ls,l,r)*query(rs,l,r);
	}
}T;
signed main(){
	scanf("%lld%lld",&n,&q);
	T.build(1,1,n);
	while(q--){
		char op;
		ll x,y;
		scanf(" %c%lld",&op,&x);
		x++;
		if(op=='x') scanf("%lld",&y),T.update(1,x,y,0);
		else if(op=='y') scanf("%lld",&y),T.update(1,x,y,1);
		else{
			if(x==1) puts("1");
			else{
				Matrix ans;
				ans.a[1][1]=ans.a[1][2]=ans.a[1][3]=ans.a[1][4]=1;
				ans=ans*T.query(1,1,x-1);
				printf("%lld\n",ans.a[1][1]);
			}
		}
	}
}
0