結果

問題 No.2265 Xor Range Substring Sum Query
ユーザー lgswdnlgswdn
提出日時 2023-05-04 17:09:24
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,845 ms / 5,000 ms
コード長 2,548 bytes
コンパイル時間 2,430 ms
コンパイル使用メモリ 206,344 KB
実行使用メモリ 19,588 KB
最終ジャッジ日時 2024-11-22 09:14:31
合計ジャッジ時間 27,277 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 3 ms
5,248 KB
testcase_03 AC 3 ms
5,248 KB
testcase_04 AC 1,075 ms
16,256 KB
testcase_05 AC 1,065 ms
16,256 KB
testcase_06 AC 1,081 ms
16,128 KB
testcase_07 AC 1,072 ms
16,256 KB
testcase_08 AC 1,072 ms
18,612 KB
testcase_09 AC 1,329 ms
18,844 KB
testcase_10 AC 1,328 ms
18,528 KB
testcase_11 AC 1,322 ms
19,140 KB
testcase_12 AC 1,319 ms
18,744 KB
testcase_13 AC 1,307 ms
18,436 KB
testcase_14 AC 834 ms
18,552 KB
testcase_15 AC 832 ms
18,764 KB
testcase_16 AC 839 ms
18,744 KB
testcase_17 AC 839 ms
19,480 KB
testcase_18 AC 1,283 ms
18,972 KB
testcase_19 AC 1,310 ms
18,296 KB
testcase_20 AC 1,841 ms
18,720 KB
testcase_21 AC 1,845 ms
19,588 KB
testcase_22 AC 441 ms
17,256 KB
testcase_23 AC 439 ms
17,008 KB
権限があれば一括ダウンロードができます

ソースコード

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],tick;
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 BLT {
  int S,b[N],c[N],l[N],id[N],tot,bs;
  vi s[520];
  void build(int p,int l,int r) {
    s[p].resize(bs);
    rep(x,0,bs-1) {
      s[p][x]=0;
      rep(j,l,r) c[j^x]=a[j];
      rep(j,l,r) s[p][x]=(s[p][x]+c[j]*w[j-l+1])%mod;
    }
  }
  void bmdf(int p,int l,int r,int x,int y) {
    rep(z,0,bs-1) {
      int pos=z^x;
      s[p][z]=(s[p][z]+y*w[pos-l+1])%mod;
    }
  }
  pii bqry(int p,int l,int r,int x,int y,int z) {
    if(r<x||l>y) return pii(0,0);
    else if(x<=l&&r<=y) return pii(r-l+1,s[p][z]);
    else {
      x=max(x,l), y=min(y,r); int cnt=0,res=0;
      rep(i,x,y) res=(res+a[i^z]*w[++cnt])%mod;
      return pii(cnt,res);
    }
  }
  void build(int n) {
    S=(1<<n)-1; bs=1<<(n/2);
    rep(i,0,S) b[i]=i/bs; tot=b[S];
    rep(i,0,tot) l[i]=i*bs;
    rep(i,0,tot) build(i,l[i],l[i]+bs-1);
  }
  void mdf(int x,int y) {
    bmdf(b[x],l[b[x]],l[b[x]]+bs-1,x,(y-a[x]+mod)%mod); a[x]=y;
  }
  int qry(int x,int y,int z) {
    int z1=z/bs, z2=z&(bs-1), cnt=0, ans=0;
    rep(i,0,tot) id[i]=i^z1;
    rep(i,0,tot) {
      int p=id[i]; int x0=max(x,l[i]), y0=min(y,l[i]+bs-1);
      if(x0>y0) continue; x0^=z1*bs, y0^=z1*bs;
      auto [c,r]=bqry(p,l[p],l[p]+bs-1,x0,y0,z2);
      if(c) ans=(ans+w[cnt]*r)%mod, cnt+=c;
    } return ans;
  }
}

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;
  BLT::build(n);
  for(int Q=read();Q;Q--) {
    int op=read();
    if(op==1) {
      int x=read(), y=read();
      BLT::mdf(x,y);
    } else {
      int l=read(), r=read(), b=read();
      int res=BLT::qry(l,r,b);
      printf("%lld\n",res*t[r-l+1]%mod);
    }
  }
  return 0;
}
0