結果

問題 No.3478 XOR-Folding Primes
コンテスト
ユーザー 👑 tails
提出日時 2026-03-21 01:58:53
言語 cLay
(20250308-1 + boost 1.89.0)
コンパイル:
clayc _filename_
実行:
./a.out
結果
AC  
実行時間 189 ms / 4,000 ms
コード長 389 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,577 ms
コンパイル使用メモリ 200,840 KB
実行使用メモリ 127,556 KB
最終ジャッジ日時 2026-03-21 01:59:00
合計ジャッジ時間 5,878 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#define MD 998244353
int p[7d5],q[1d7]{},r[1d7],s[1d7];
ll np=Prime(1d7,p);
rep(i,np){
	q[p[i]]=1;
}
int a=0,b=0;
rep(i,1d7){
	r[i]=a+=q[i];
	s[i]=b;
	b+=q[i]*q[i^2];
	if(i>(i^2)){
		s[i]=b;
	}
}
ll@t;
rep(t){
	ll@n,@m;
	if(n==1){
		wt(r[m]);
	}else{
		Matrix<Mint>a(2,2);
		a[0][0]=0;
		a[0][1]=1;
		a[1][0]=s[m];
		a[1][1]=1;
		a**=n-1;
		wt(a[0][0]+a[1][0]+s[m]*(a[0][1]+a[1][1]));
	}
}
0