結果

問題 No.1891 Static Xor Range Composite Query
ユーザー tailstails
提出日時 2022-04-04 19:46:11
言語 cLay
(20231016-1)
結果
AC  
実行時間 260 ms / 5,000 ms
コード長 507 bytes
コンパイル時間 3,539 ms
コンパイル使用メモリ 174,072 KB
実行使用メモリ 45,560 KB
最終ジャッジ日時 2023-08-16 21:50:22
合計ジャッジ時間 11,049 ms
ジャッジサーバーID
(参考情報)
judge12 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 52 ms
44,532 KB
testcase_01 AC 53 ms
44,288 KB
testcase_02 AC 52 ms
44,272 KB
testcase_03 AC 52 ms
44,288 KB
testcase_04 AC 52 ms
44,392 KB
testcase_05 AC 52 ms
44,408 KB
testcase_06 AC 52 ms
44,308 KB
testcase_07 AC 52 ms
44,496 KB
testcase_08 AC 52 ms
44,548 KB
testcase_09 AC 52 ms
44,552 KB
testcase_10 AC 53 ms
44,324 KB
testcase_11 AC 53 ms
44,416 KB
testcase_12 AC 53 ms
44,596 KB
testcase_13 AC 53 ms
44,356 KB
testcase_14 AC 53 ms
44,612 KB
testcase_15 AC 53 ms
44,356 KB
testcase_16 AC 53 ms
44,392 KB
testcase_17 AC 53 ms
44,424 KB
testcase_18 AC 54 ms
44,368 KB
testcase_19 AC 53 ms
44,392 KB
testcase_20 AC 53 ms
44,392 KB
testcase_21 AC 256 ms
45,340 KB
testcase_22 AC 255 ms
45,428 KB
testcase_23 AC 255 ms
45,560 KB
testcase_24 AC 255 ms
45,360 KB
testcase_25 AC 260 ms
45,300 KB
testcase_26 AC 253 ms
45,380 KB
testcase_27 AC 249 ms
45,364 KB
testcase_28 AC 251 ms
45,304 KB
testcase_29 AC 250 ms
45,436 KB
testcase_30 AC 248 ms
45,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#define MD 998244353

struct AB {
	Mint a,b;
};

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

AB ab[19][262144];

{
	ll@n,@q;
	rep(i,n){
		rd(ab[0][i].a,ab[0][i].b);
	}
	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{1,0};
		AB v{1,0};
		ll d=0;
		while(l<r){
			ll m=1<<d;
			if(l&m){
				u=u*ab[d][l^p];
				l+=m;
			}
			if(r&m){
				r-=m;
				v=ab[d][r^p]*v;
			}
			++d;
		}
		u=u*v;
		wt(u.a*x+u.b);
	}
}
0