結果

問題 No.749 クエリ全部盛り
ユーザー 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
提出日時 2018-10-07 00:41:06
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 2,989 bytes
コンパイル時間 777 ms
コンパイル使用メモリ 80,232 KB
実行使用メモリ 41,924 KB
最終ジャッジ日時 2024-04-20 18:07:33
合計ジャッジ時間 9,611 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 16 ms
35,288 KB
testcase_01 AC 22 ms
34,944 KB
testcase_02 AC 17 ms
34,868 KB
testcase_03 AC 21 ms
34,944 KB
testcase_04 AC 16 ms
35,024 KB
testcase_05 AC 27 ms
34,816 KB
testcase_06 AC 21 ms
34,952 KB
testcase_07 AC 28 ms
34,816 KB
testcase_08 AC 22 ms
34,960 KB
testcase_09 AC 28 ms
34,944 KB
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<vector>
#include<cassert>
using namespace std;
typedef long long lint;
typedef vector<int>vi;
typedef pair<int,int>pii;
typedef pair<lint,lint>pll;
#define rep(i,n)for(int i=0;i<(int)(n);++i)
const lint mo=1e9+7;

const int N=1000000;
const int A=1000;
const int B=N/A;
lint a[N];
lint asum[A];
lint u[A],v[A];
lint tap[A];
pll phi[N];
pll phiacc[N+1];
pll add(pll a,pll b){
  return pll((a.first+b.first)%mo,(a.second+b.second)%mo);
}
pll mul(pll a,pll b){
  lint x=a.first*b.first+5*a.second*b.second;
  lint y=a.first*b.second+a.second*b.first;
  return pll(x%mo,y%mo);
}

void init(){
  pll p((mo+1)/2,(mo+1)/2);
  pll c(1,0);
  rep(i,N){
    phi[i]=c;
    phiacc[i+1]=add(phiacc[i],phi[i]);
    c=mul(c,p);
  }
}

void red(int k){
  if(k>=A)return;
  lint tmp=0;
  rep(i,B){
    int idx=k*B+i;
    a[idx]=u[k]*a[idx]+v[k]+2*tap[k]*phi[idx].second;
    a[idx]%=mo;
    tmp=(tmp+a[idx])%mo;
  }
  u[k]=1;
  v[k]=0;
  tap[k]=0;
  asum[k]=tmp;
}
void upd_n_sx_plus_t(int l,int r,int s,int t){
  assert(r<=l/B*B+B);
  if(l>=r)return;
  red(l/B);
  lint tmp=asum[l/B];
  for(int i=l;i<r;i++){
    tmp+=mo-a[i];
    a[i]=(a[i]*s+t)%mo;
    tmp+=a[i];
  }
  asum[l/B]=tmp%mo;
}
void upd_sx_plus_t(int l,int r,int s,int t){
  assert(l<=r);
  if((l+B-1)/B>=r/B){
    upd_n_sx_plus_t(l,r,s,t);
    return;
  }
  int lb=(l+B-1)/B;
  int rb=r/B;
  upd_n_sx_plus_t(l,B*lb,s,t);
  upd_n_sx_plus_t(B*rb,r,s,t);
  for(int i=lb;i<rb;++i){
    u[i]=u[i]*s%mo;
    v[i]=(v[i]*s+t)%mo;
    tap[i]=tap[i]*s%mo;
  }
}
void upd_n_fib(int l,int r,int k){
  assert(r<=l/B*B+B);
  if(l>=r)return;
  red(l/B);
  lint tmp=asum[l/B];
  for(int i=l;i<r;i++){
    tmp+=mo-a[i];
    a[i]=(a[i]+2*phi[i].second*k)%mo;
    tmp+=a[i];
  }
  asum[l/B]=tmp%mo;
}
void upd_fib(int l,int r,int k){
  assert(l<=r);
  if((l+B-1)/B>=r/B){
    upd_n_fib(l,r,k);
    return;
  }
  int lb=(l+B-1)/B;
  int rb=r/B;
  upd_n_fib(l,B*lb,k);
  upd_n_fib(B*rb,r,k);
  for(int i=lb;i<rb;++i){
    tap[i]=(tap[i]+k)%mo;
  }
}

lint calc_n(int l,int r){
  assert(r<=l/B*B+B);
  if(l>=r)return 0;
  red(l/B);
  lint ans=0;
  for(int i=l;i<r;i++)ans=(ans+a[i])%mo;
  return ans;
}

lint calc(int l,int r){
  assert(l<=r);
  if((l+B-1)/B>=r/B){
    return calc_n(l,r);
  }
  int lb=(l+B-1)/B;
  int rb=r/B;
  lint ans=0;
  ans=calc_n(l,B*lb);
  ans+=calc_n(B*rb,r);
  for(int i=lb;i<rb;++i){
    ans+=u[i]*asum[i]%mo;
    ans+=v[i]*B;
    ans+=2*tap[i]*(phiacc[i*B+B].second-phiacc[i*B].second+mo)%mo;
    ans%=mo;
  }
  return ans;
}

int main(){
  init();
  int n,q;
  scanf("%d%d",&n,&q);
  rep(_,q){
    int kind,l,r,k;
    scanf("%d%d%d%d",&kind,&l,&r,&k);
    r++;
    switch(kind){
    case 0:
      printf("%lld\n",k*calc(l,r)%mo);
      break;
    case 1:
      upd_sx_plus_t(l,r,0,k);
      break;
    case 2:
      upd_sx_plus_t(l,r,1,k);
      break;
    case 3:
      upd_sx_plus_t(l,r,k,0);
      break;
    case 4:
      upd_fib(l,r,k);
      break;
    }
  }
}
0