#751780 (cLay) No.1891 Static Xor Range Composite Query

• 問題: No.1891 Static Xor Range Composite Query
• ユーザー: tails
• 提出日時: 2022-04-04 19:46:11
• 言語: cLay (20240714-1)
• 結果: AC
• 実行時間: 247 ms / 5,000 ms
• コード長: 507 bytes
• コンパイル時間: 4,033 ms
• コンパイル使用メモリ: 177,476 KB
• 実行使用メモリ: 44,544 KB
• 最終ジャッジ日時: 2024-11-25 12:27:44
• 合計ジャッジ時間: 13,248 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	59 ms; 43,772 KB
testcase_01	AC	58 ms; 44,384 KB
testcase_02	AC	59 ms; 43,920 KB
testcase_03	AC	59 ms; 44,492 KB
testcase_04	AC	59 ms; 44,084 KB
testcase_05	AC	58 ms; 44,096 KB
testcase_06	AC	60 ms; 44,460 KB
testcase_07	AC	58 ms; 44,160 KB
testcase_08	AC	58 ms; 44,128 KB
testcase_09	AC	59 ms; 44,468 KB
testcase_10	AC	59 ms; 43,564 KB
testcase_11	AC	58 ms; 44,364 KB
testcase_12	AC	58 ms; 42,496 KB
testcase_13	AC	57 ms; 42,368 KB
testcase_14	AC	59 ms; 42,496 KB
testcase_15	AC	63 ms; 42,240 KB
testcase_16	AC	59 ms; 42,368 KB
testcase_17	AC	59 ms; 42,496 KB
testcase_18	AC	58 ms; 42,240 KB
testcase_19	AC	59 ms; 42,368 KB
testcase_20	AC	57 ms; 42,496 KB
testcase_21	AC	241 ms; 44,288 KB
testcase_22	AC	237 ms; 44,416 KB
testcase_23	AC	247 ms; 44,288 KB
testcase_24	AC	238 ms; 44,288 KB
testcase_25	AC	238 ms; 44,416 KB
testcase_26	AC	243 ms; 44,416 KB
testcase_27	AC	240 ms; 44,288 KB
testcase_28	AC	241 ms; 44,288 KB
testcase_29	AC	235 ms; 44,544 KB
testcase_30	AC	244 ms; 44,416 KB

ソースコード

#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);
	}
}