結果

問題 No.3033 エルハートの数え上げ
コンテスト
ユーザー ジュ・ビオレ・グレイス
提出日時 2025-01-31 20:16:26
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 1,419 ms / 2,000 ms
コード長 1,350 bytes
コンパイル時間 1,828 ms
コンパイル使用メモリ 95,116 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-02-21 20:50:26
合計ジャッジ時間 25,617 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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

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, i4;
	foreach (x; -99 .. 100) foreach (y; -99 .. 100) foreach (z; -99 .. 100) {
		if (half_spaces.all!(hs => inside(hs,x,y,z,1))) i1++;
		if (half_spaces.all!(hs => inside(hs,x,y,z,2))) i2++;
		if (half_spaces.all!(hs => inside(hs,x,y,z,3))) i3++;
		if (half_spaces.all!(hs => inside(hs,x,y,z,4))) i4++;
	}
	i1 %= p, i2 %= p, i3 %= p, i4 %= p;
	
	long
		a0 = -inv6    *i1 + 3*inv6  *i2 - 3*inv6  *i3 + inv6    *i4,
		a1 = 9*inv6   *i1 - 4       *i2 + 21*inv6 *i3 -          i4,
		a2 = -26*inv6 *i1 + 57*inv6 *i2 - 7       *i3 + 11*inv6 *i4,
		a3 = 4        *i1 - 6       *i2 + 4       *i3 -          i4;
	a0 %= p, a1 %= p, a2 %= p, a3 %= p;
	if (a0 < 0) a0 += p;
	if (a1 < 0) a1 += p;
	if (a2 < 0) a2 += p;
	if (a3 < 0) a3 += p;
	
	writeln( ((a0*N%p*N%p*N%p) + (a1*N%p*N%p) + (a2*N%p) + a3 ) % p );
}
0