結果

問題 No.1891 Static Xor Range Composite Query
ユーザー tailstails
提出日時 2022-04-04 19:17:14
言語 cLay
(20240714-1)
結果
AC  
実行時間 313 ms / 5,000 ms
コード長 589 bytes
コンパイル時間 2,881 ms
コンパイル使用メモリ 179,824 KB
実行使用メモリ 45,964 KB
最終ジャッジ日時 2024-05-04 04:44:13
合計ジャッジ時間 9,604 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 51 ms
42,240 KB
testcase_01 AC 54 ms
43,348 KB
testcase_02 AC 51 ms
42,240 KB
testcase_03 AC 52 ms
44,224 KB
testcase_04 AC 51 ms
42,240 KB
testcase_05 AC 52 ms
43,444 KB
testcase_06 AC 49 ms
42,240 KB
testcase_07 AC 50 ms
44,312 KB
testcase_08 AC 51 ms
42,368 KB
testcase_09 AC 50 ms
44,408 KB
testcase_10 AC 49 ms
42,368 KB
testcase_11 AC 53 ms
44,544 KB
testcase_12 AC 53 ms
42,496 KB
testcase_13 AC 53 ms
43,428 KB
testcase_14 AC 52 ms
42,496 KB
testcase_15 AC 52 ms
44,076 KB
testcase_16 AC 54 ms
42,240 KB
testcase_17 AC 52 ms
44,240 KB
testcase_18 AC 53 ms
42,368 KB
testcase_19 AC 52 ms
44,088 KB
testcase_20 AC 51 ms
42,368 KB
testcase_21 AC 294 ms
44,992 KB
testcase_22 AC 307 ms
44,288 KB
testcase_23 AC 297 ms
45,964 KB
testcase_24 AC 305 ms
44,288 KB
testcase_25 AC 294 ms
45,812 KB
testcase_26 AC 294 ms
44,416 KB
testcase_27 AC 313 ms
45,392 KB
testcase_28 AC 296 ms
44,416 KB
testcase_29 AC 294 ms
45,736 KB
testcase_30 AC 292 ms
44,416 KB
権限があれば一括ダウンロードができます

ソースコード

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