Codeforces Round #FF Div2 E DZY Loves Fibonacci Numbers
最初みたとき解法が全然わからなかったけど以下の2点に気づくだけだった
・フィボナッチ数列同士を足した数列もフィボナッチ数列である
・初項、第2項がa,bのフィボナッチ数列の第n項は基本のフィボナッチ数列をfib[n]としてa*fib[n-1]+b*fib[n-2]とO(1)で求められる
あとは適当に遅延評価segtreeを書くだけなんだけどMODの闇にはまってしまって18WA出してしまった。この前もMODのせいでHackされたし気をつけます
99%正しいコードから通すまで2日かけてしまった。最高の夏の幕開けが…
デバッグ用の関数消すのめんどくさかったんで許してください
#include <cstdio> #include <iostream> using namespace std; typedef long long ll; #define MOD 1000000009 const int SIZE=1<<19; ll fib[300100]; int n,m; ll lazy1[SIZE*2],lazy2[SIZE*2]; ll sum[SIZE*2]; void compute_fib() { fib[1]=1ll; fib[2]=1ll; for(int i=3;i<=300000;i++)fib[i]=(fib[i-1]+fib[i-2])%MOD; return; } ll compute_num(ll a,ll b,int n) { if(n==1)return a; if(n==2)return b; return ((a*fib[n-2])%MOD+(b*fib[n-1])%MOD)%MOD; } void init() { scanf("%d %d",&n,&m); for(int i=0;i<n;i++)scanf("%I64d",&sum[SIZE-1+i]); for(int i=SIZE-2;i>=0;i--)sum[i]=(sum[i*2+1]+sum[i*2+2])%MOD; return; } void lazy_evaluate(int k,int l,int r) { if(lazy1[k]||lazy2[k]) { sum[k]+=compute_num(lazy1[k],lazy2[k],r-l+2)-lazy2[k]; while(sum[k]<0)sum[k]+=MOD; sum[k]%=MOD; } if(k<SIZE-1) { lazy1[k*2+1]+=lazy1[k]; lazy2[k*2+1]+=lazy2[k]; lazy1[k*2+1]%=MOD; lazy2[k*2+1]%=MOD; lazy1[k*2+2]+=compute_num(lazy1[k],lazy2[k],(l+r)/2-l+1); lazy1[k*2+2]%=MOD; lazy2[k*2+2]+=compute_num(lazy1[k],lazy2[k],(l+r)/2-l+2); lazy2[k*2+2]%=MOD; } lazy1[k]=0; lazy2[k]=0; return; } void update(int a,int b,int sa,int sb,int k,int l,int r,ll x1,ll x2) { lazy_evaluate(k,l,r); if(r<=a||b<=l)return; else if(a<=l&&r<=b) { lazy1[k]=x1; lazy2[k]=x2; lazy_evaluate(k,l,r); } else { if(sb<=(l+r)/2) { update(a,b,sa,sb,k*2+1,l,(l+r)/2,x1,x2); lazy_evaluate(k*2+2,(l+r)/2,r); } else if(sa>=(l+r)/2) { lazy_evaluate(k*2+1,l,(l+r)/2); update(a,b,sa,sb,k*2+2,(l+r)/2,r,x1,x2); } else { ll nx1=compute_num(x1,x2,(l+r)/2-sa+1); ll nx2=compute_num(x1,x2,(l+r)/2-sa+2); update(a,b,sa,(l+r)/2,k*2+1,l,(l+r)/2,x1,x2); update(a,b,(l+r)/2,sb,k*2+2,(l+r)/2,r,nx1,nx2); } sum[k]=(sum[k*2+1]+sum[k*2+2])%MOD; } } ll query(int a,int b,int k,int l,int r) { lazy_evaluate(k,l,r); if(r<=a||b<=l)return 0ll; else if(a<=l&&r<=b)return sum[k]; else { ll lch=query(a,b,k*2+1,l,(l+r)/2); ll rch=query(a,b,k*2+2,(l+r)/2,r); sum[k]=(sum[k*2+1]+sum[k*2+2])%MOD; return (lch+rch)%MOD; } } void print_tree() { int num=0; for(int i=0;i<5;i++) { for(int j=0;j<(4-i)*4;j++)cout << ' '; for(int j=0;j<(1<<i);j++) { printf("%I64d[%d][%d] ",sum[num+j],lazy1[num+j],lazy2[num+j]); } num+=(1<<i); cout << endl; } return; } int main() { init(); compute_fib(); for(int i=0;i<m;i++) { int type,l,r; scanf("%d %d %d",&type,&l,&r); l--; if(type==1)update(l,r,l,r,0,0,SIZE,1,1); else printf("%I64d\n",query(l,r,0,0,SIZE)); //print_tree(); } return 0; }