結果
問題 |
No.510 二次漸化式
|
ユーザー |
![]() |
提出日時 | 2025-02-28 21:05:10 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,930 bytes |
コンパイル時間 | 3,786 ms |
コンパイル使用メモリ | 276,128 KB |
実行使用メモリ | 16,524 KB |
最終ジャッジ日時 | 2025-02-28 21:06:03 |
合計ジャッジ時間 | 26,807 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 2 |
other | AC * 1 WA * 21 TLE * 9 -- * 3 |
ソースコード
#include<bits/stdc++.h> #define int long long #define maxn 100005 using namespace std; const int mod=1e9+7; inline int ksm(int d,int z){ int res=1; while(z){ if(z&1)res=(res*d)%mod; d=(d*d)%mod;z>>=1; } return res; } int n,q,a[maxn],b[maxn],x[maxn],y[maxn],chafen[maxn]; int block,blo[maxn],blol[maxn],blor[maxn],tag[maxn]; inline int pf(int x){return (x*x%mod);} inline int lowbit(int x){return x&(-x);} inline void update(int id,int dt){ for(int i=id;i<=n;i+=lowbit(i)) chafen[i]+=dt; } inline int query(int id){ int sum=0; for(int i=id;i;i-=lowbit(i)) sum+=chafen[i]; return sum; } inline void modifyy(int id,int v){ int delta=v-y[id];delta=(delta%mod+mod)%mod; y[id]=v;int mul=delta*b[id]%mod; for(int i=id+1;i<=n;++i){ int DEL=(pf(mul)+2*b[i]*mul)%mod; chafen[i]=(chafen[i]+x[i]*((2*b[i]*DEL+pf(DEL))%mod)%mod)%mod; b[i]=(b[i]+mul)%mod;mul=(mul*y[i])%mod; } return; } inline void modifyx(int id,int v){ x[id]=v;chafen[id+1]=(v*pf(b[id]))%mod; return; } inline int ask(int id){ int s=1; for(int i=1;i<=id;++i) s+=chafen[i]; return s%mod; } signed main(){ // freopen("generator.in","r",stdin); // freopen("generator.out","w",stdout); ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>q;a[0]=b[0]=1;block=sqrt(n); for(int i=1;i<=n;++i){ b[i]=(y[i-1]*b[i-1]+1)%mod; a[i]=(x[i-1]*pf(b[i-1])+a[i-1])%mod; chafen[i]=a[i]-a[i-1]; blo[i]=(i-1)/block+1; if(!blol[blo[i]])blol[blo[i]]=i; blor[blo[i]]=i; } while(q--){ char op;cin>>op; if(op=='x'){ int i,v;cin>>i>>v; modifyx(i,v); } else if(op=='y'){ int i,v;cin>>i>>v; modifyy(i,v); } else{ int k;cin>>k; cout<<ask(k)<<"\n"; } } return 0; }