結果
問題 |
No.510 二次漸化式
|
ユーザー |
![]() |
提出日時 | 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); | ~~~~~^~~~~~~~~
ソースコード
#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; }