結果

問題 No.1891 Static Xor Range Composite Query
ユーザー tailstails
提出日時 2022-04-04 19:17:14
言語 cLay
(20241019-1)
結果
AC  
実行時間 350 ms / 5,000 ms
コード長 589 bytes
コンパイル時間 3,183 ms
コンパイル使用メモリ 178,968 KB
実行使用メモリ 47,480 KB
最終ジャッジ日時 2024-11-25 11:53:14
合計ジャッジ時間 10,489 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define MD 998244353

struct AB {
	Mint a,b;
};

AB operator*(AB x,AB y){
	return {y.a*x.a,y.a*x.b+y.b};
}

AB ab[19][262144];

AB f(ll l,ll p){
	AB x{1,0};
	if(l==0){
		x=ab[18][p];
	}else{
		for(ll d=0;d<18;++d){
			if(l&1<<d){
				x=x*ab[d][l^p];
				l+=1<<d;
			}
		}
	}
	return x;
}

{
	ll@n,@q;
	rep(i,n){
		rd(ab[0][i].a,ab[0][i].b);
	}
	rep(i,n,262144){
		ab[0][i]=AB{1,0};
	}
	rep(d,1,19){
		ll m=1<<d-1;
		rep(i,262144){
			ab[d][i]=ab[d-1][i]*ab[d-1][i^m];
		}
	}
	rep(q){
		ll@l,@r,@p,@x;
		AB u=f(l,p);
		AB v=f(r,p);
		u.b-=v.b;
		u.a/=v.a;
		u.b/=v.a;
		wt(u.a*x+u.b);
	}
}
0