結果

問題 No.510 二次漸化式
コンテスト
ユーザー vjudge1
提出日時 2025-02-23 18:22:30
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 25 ms / 3,000 ms
コード長 1,776 bytes
コンパイル時間 1,560 ms
コンパイル使用メモリ 163,108 KB
実行使用メモリ 16,972 KB
最終ジャッジ日時 2025-02-23 18:22:35
合計ジャッジ時間 4,774 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:56:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   56 |         scanf("%d%d",&n,&q);
      |         ~~~~~^~~~~~~~~~~~~~
main.cpp:60:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   60 |                 scanf("%s",op+1);
      |                 ~~~~~^~~~~~~~~~~
main.cpp:62:38: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   62 |                         int i,v;scanf("%d%d",&i,&v);
      |                                 ~~~~~^~~~~~~~~~~~~~
main.cpp:66:38: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   66 |                         int i,v;scanf("%d%d",&i,&v);
      |                                 ~~~~~^~~~~~~~~~~~~~
main.cpp:71:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   71 |                         int i;scanf("%d",&i);
      |                               ~~~~~^~~~~~~~~

ソースコード

diff # 

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
struct matr{
	int a12,a13,a14;
	int a22,a23,a24;
	int a33,a34;
}li,sm[400005],ss[100005];
inline matr operator*(matr a,matr b){
	matr c=li;
	c.a12=(b.a12+1ll*a.a12*b.a22)%mod;
	c.a13=(b.a13+1ll*a.a12*b.a23+1ll*a.a13*b.a33)%mod;
	c.a14=(a.a14+b.a14+1ll*a.a13*b.a34+1ll*a.a12*b.a24)%mod;
	c.a22=(1ll*a.a22*b.a22)%mod;
	c.a23=(1ll*a.a22*b.a23+1ll*a.a23*b.a33)%mod;
	c.a24=(a.a24+1ll*a.a22*b.a24+1ll*a.a23*b.a34)%mod;
	c.a33=(1ll*a.a33*b.a33)%mod;
	c.a34=(a.a34+1ll*a.a33*b.a34)%mod;
	return c;
}
void build(int l,int r,int o){
	sm[o].a12=sm[o].a13=1;
	if(l==r){
		ss[l]=sm[o];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,o<<1);build(mid+1,r,o<<1|1);
}
void add(int l,int r,int o,int x){
	if(l==r){
		sm[o]=ss[x];
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)add(l,mid,o<<1,x);
	else add(mid+1,r,o<<1|1,x);
	sm[o]=sm[o<<1]*sm[o<<1|1];
}
int a2,a3,a4;
int b2,b3,b4;
void query(int l,int r,int o,int ll,int rr){
	if(l>=ll&&r<=rr){
		b2=(1ll*a2*sm[o].a22+sm[o].a12)%mod;
		b3=(1ll*a2*sm[o].a23+1ll*a3*sm[o].a33+sm[o].a13)%mod;
		b4=(1ll*a2*sm[o].a24+1ll*a3*sm[o].a34+a4+sm[o].a14)%mod;
		a2=b2,a3=b3,a4=b4;
		return;
	}
	int mid=(l+r)>>1;
	if(mid>=ll)query(l,mid,o<<1,ll,rr);
	if(mid<rr)query(mid+1,r,o<<1|1,ll,rr);
}
int main(){
	int n,q;
	scanf("%d%d",&n,&q);
	build(0,n-1,1);
	while(q--){
		char op[15];
		scanf("%s",op+1);
		if(op[1]=='x'){
			int i,v;scanf("%d%d",&i,&v);
			ss[i].a34=v;
			add(0,n-1,1,i);
		}else if(op[1]=='y'){
			int i,v;scanf("%d%d",&i,&v);
			ss[i].a22=v;ss[i].a23=2*v%mod;
			ss[i].a33=1ll*v*v%mod;
			add(0,n-1,1,i);
		}else{
			int i;scanf("%d",&i);
			if(i==0){
				printf("%d\n",1);
				continue;
			}
			a2=a3=a4=1;
			query(0,n-1,1,0,i-1);
			printf("%d\n",a4);
		}
	}
	return 0;
}
0