結果

問題 No.2265 Xor Range Substring Sum Query
ユーザー lgswdnlgswdn
提出日時 2023-05-04 13:04:06
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,947 bytes
コンパイル時間 2,198 ms
コンパイル使用メモリ 204,728 KB
実行使用メモリ 99,712 KB
最終ジャッジ日時 2024-11-22 06:18:22
合計ジャッジ時間 104,041 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 12 ms
99,584 KB
testcase_01 AC 11 ms
99,712 KB
testcase_02 AC 12 ms
21,248 KB
testcase_03 AC 11 ms
99,456 KB
testcase_04 TLE -
testcase_05 TLE -
testcase_06 TLE -
testcase_07 TLE -
testcase_08 TLE -
testcase_09 TLE -
testcase_10 TLE -
testcase_11 TLE -
testcase_12 TLE -
testcase_13 TLE -
testcase_14 TLE -
testcase_15 TLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 AC 654 ms
83,712 KB
testcase_19 AC 668 ms
83,584 KB
testcase_20 AC 745 ms
83,584 KB
testcase_21 AC 733 ms
83,712 KB
testcase_22 TLE -
testcase_23 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define fi first
#define se second
#define eb emplace_back
#define popc __builtin_popcount
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef unsigned long long ull;
typedef long double ld;

int read() {
  int x=0,w=1; char c=getchar(); 
  while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
  while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
  return x*w;
}

const int N=(1<<18)+9,mod=998244353,inv2=(mod+1)/2;
int n,a[N],w[N],q,t[N];
char s[N];

int ksm(int x,int y,int r=1) {
  for(;y;y>>=1,x=x*x%mod) if(y&1) r=r*x%mod;
  return r;
}

namespace Trie {
  int tot=1,ls[N<<1],rs[N<<1],h[N<<1];
  vi s[N<<1];
  void build(int p,int l,int r) {
    if(l==r) {
      h[p]=0; s[p].resize(1);
      s[p][0]=q*a[l]%mod; return;
    } int mid=l+r>>1;
    build(ls[p]=++tot,l,mid);
    build(rs[p]=++tot,mid+1,r);
    h[p]=h[ls[p]]+1; s[p].resize(1<<h[p]);
    rep(j,0,(1<<h[p])-1) {
      int x=j;
      if(!(j&(1<<h[p]-1))) s[p][j]=(s[ls[p]][x]+s[rs[p]][x]*w[mid-l+1])%mod;
      else x^=(1<<h[p]-1), s[p][j]=(s[rs[p]][x]+s[ls[p]][x]*w[r-mid])%mod;
    }
  }
  void mdf(int p,int l,int r,int x,int y) {
    if(l==r) {s[p][0]=q*y%mod; return;} int mid=l+r>>1;
    if(x<=mid) mdf(ls[p],l,mid,x,y);
    else mdf(rs[p],mid+1,r,x,y);
    rep(j,0,(1<<h[p])-1) {
      int x=j;
      if(!(j&(1<<h[p]-1))) s[p][j]=(s[ls[p]][x]+s[rs[p]][x]*w[mid-l+1])%mod;
      else x^=(1<<h[p]-1), s[p][j]=(s[rs[p]][x]+s[ls[p]][x]*w[r-mid])%mod;
    }
  }
  int qry(int p,int l,int r,int x,int y,int h,int b) {
    if(l==x&&r==y) return s[p][b&((1<<h)-1)]; int mid=l+r>>1;
    if(y<=mid) {
      if(!(b&(1<<h-1))) return qry(ls[p],l,mid,x,y,h-1,b);
      else return qry(rs[p],mid+1,r,x^(1<<h-1),y^(1<<h-1),h-1,b);
    } else if(x>mid) {
      if(!(b&(1<<h-1))) return qry(rs[p],mid+1,r,x,y,h-1,b);
      else return qry(ls[p],l,mid,x^(1<<h-1),y^(1<<h-1),h-1,b);
    } else {
      if(!(b&(1<<h-1))) {
        int xx=qry(ls[p],l,mid,x,mid,h-1,b);
        int yy=qry(rs[p],mid+1,r,mid+1,y,h-1,b);
        return (xx+yy*w[mid-x+1])%mod;
      } else {
        int xx=qry(ls[p],l,mid,l,y^(1<<h-1),h-1,b);
        int yy=qry(rs[p],mid+1,r,x^(1<<h-1),r,h-1,b);
        return (yy+xx*w[mid-x+1])%mod;
      }
    }
  }
}

signed main() {
  scanf("%lld%s",&n,s); int lim=(1<<n)-1;
  rep(i,0,lim) a[i]=s[i]-'0';
  w[0]=t[0]=1; q=2*ksm(11,mod-2)%mod;
  rep(i,1,lim+1) t[i]=t[i-1]*11%mod;
  rep(i,1,lim+1) t[i]=t[i]*ksm(2,mod-2)%mod;
  rep(i,1,lim+1) w[i]=w[i-1]*q%mod;
  Trie::build(1,0,lim);
  for(int Q=read();Q;Q--) {
    int op=read();
    if(op==1) {
      int x=read(), y=read();
      Trie::mdf(1,0,lim,x,y);
    } else {
      int l=read(), r=read(), b=read();
      int res=Trie::qry(1,0,lim,l,r,n,b);
      printf("%lld\n",res*t[r-l+1]%mod);
    }
  }
  return 0;
}
0