結果

問題 No.3033 エルハートの数え上げ
コンテスト
ユーザー ジュ・ビオレ・グレイス
提出日時 2025-02-02 18:03:24
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 261 ms / 2,000 ms
コード長 1,376 bytes
コンパイル時間 803 ms
コンパイル使用メモリ 96,068 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2025-02-21 20:51:05
合計ジャッジ時間 6,004 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.algorithm, std.array, std.container, std.conv, std.math, std.range, std.stdio, std.typecons;

immutable long p = 998244353;
immutable long inv6 = 166374059;	// inv6 * 6 % p = 1
immutable Mmax = 25;

void main() {
	auto NM = readln.split.to!(uint[]);
	auto N = NM[0] % p, M = NM[1];
	long[][] half_spaces;
	foreach (m; 0 .. M) {
		half_spaces ~= readln.split.to!(long[]);
	}
	
	bool inside(long[] half_space, long x, long y, long z, long n) {
		return (half_space[0]*x + half_space[1]*y + half_space[2]*z + half_space[3]*n >= 0);
	}
	
	// count
	long i1, i2, i3;
	foreach (x; -Mmax .. Mmax+1) foreach (y; -Mmax .. Mmax+1) foreach (z; -Mmax .. Mmax+1) {
		if (half_spaces.all!(hs => inside(hs,x,y,z,1))) i1++;
	}
	foreach (x; 2*(-Mmax) .. 2*Mmax+1) foreach (y; 2*(-Mmax) .. 2*Mmax+1) foreach (z; 2*(-Mmax) .. 2*Mmax+1) {
		if (half_spaces.all!(hs => inside(hs,x,y,z,2))) i2++;
	}
	foreach (x; 3*(-Mmax) .. 3*Mmax+1) foreach (y; 3*(-Mmax) .. 3*Mmax+1) foreach (z; 3*(-Mmax) .. 3*Mmax+1) {
		if (half_spaces.all!(hs => inside(hs,x,y,z,3))) i3++;
	}
	i1 %= p, i2 %= p, i3 %= p;
	long
		d1 = i1 - 4,
		d2 = i2 - 10 - 4*d1,
		d3 = i3 - 20 - 10*d1 - 4*d2;
	d1 %= p, d2 %= p, d3 %= p;
	long ans = -inv6 * ( (-N+3)%p*(-N+2)%p*(-N+1)%p + d1*(-N+2)%p*(-N+1)%p*(-N)%p + d2*(-N+1)%p*(-N)%p*(-N-1)%p + d3*(-N)%p*(-N-1)%p*(-N-2)%p) % p;
	if (ans < 0) ans += p;
	
	writeln( ans );
}
0