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

• 問題: No.1891 Static Xor Range Composite Query
• ユーザー: tails
• 提出日時: 2022-04-04 19:17:14
• 言語: cLay (20240714-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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	56 ms; 44,676 KB
testcase_01	AC	56 ms; 47,112 KB
testcase_02	AC	56 ms; 43,896 KB
testcase_03	AC	56 ms; 44,552 KB
testcase_04	AC	56 ms; 47,480 KB
testcase_05	AC	57 ms; 44,332 KB
testcase_06	AC	56 ms; 47,212 KB
testcase_07	AC	56 ms; 47,156 KB
testcase_08	AC	56 ms; 44,192 KB
testcase_09	AC	54 ms; 45,892 KB
testcase_10	AC	54 ms; 44,052 KB
testcase_11	AC	57 ms; 44,792 KB
testcase_12	AC	57 ms; 44,604 KB
testcase_13	AC	58 ms; 44,524 KB
testcase_14	AC	56 ms; 44,476 KB
testcase_15	AC	57 ms; 43,984 KB
testcase_16	AC	56 ms; 44,260 KB
testcase_17	AC	56 ms; 43,948 KB
testcase_18	AC	56 ms; 44,192 KB
testcase_19	AC	55 ms; 44,868 KB
testcase_20	AC	56 ms; 44,860 KB
testcase_21	AC	346 ms; 45,524 KB
testcase_22	AC	347 ms; 45,036 KB
testcase_23	AC	342 ms; 45,204 KB
testcase_24	AC	347 ms; 45,724 KB
testcase_25	AC	337 ms; 45,576 KB
testcase_26	AC	350 ms; 45,992 KB
testcase_27	AC	348 ms; 45,844 KB
testcase_28	AC	350 ms; 46,052 KB
testcase_29	AC	344 ms; 45,644 KB
testcase_30	AC	348 ms; 45,288 KB

ソースコード

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