結果

問題 No.3033 エルハートの数え上げ
コンテスト
ユーザー ジュ・ビオレ・グレイス
提出日時 2025-02-02 17:10:49
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 694 ms / 2,000 ms
コード長 1,721 bytes
コンパイル時間 652 ms
コンパイル使用メモリ 94,912 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-02-21 20:50:56
合計ジャッジ時間 13,097 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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, i4;
	foreach (x; -Mmax+1 .. Mmax) foreach (y; -Mmax+1 .. Mmax) foreach (z; -Mmax+1 .. Mmax) {
		if (half_spaces.all!(hs => inside(hs,x,y,z,1))) i1++;
	}
	foreach (x; 2*(-Mmax)+1 .. 2*Mmax) foreach (y; 2*(-Mmax)+1 .. 2*Mmax) foreach (z; 2*(-Mmax)+1 .. 2*Mmax) {
		if (half_spaces.all!(hs => inside(hs,x,y,z,2))) i2++;
	}
	foreach (x; 3*(-Mmax)+1 .. 3*Mmax) foreach (y; 3*(-Mmax)+1 .. 3*Mmax) foreach (z; 3*(-Mmax)+1 .. 3*Mmax) {
		if (half_spaces.all!(hs => inside(hs,x,y,z,3))) i3++;
	}
	foreach (x; 4*(-Mmax)+1 .. 4*Mmax) foreach (y; 4*(-Mmax)+1 .. 4*Mmax) foreach (z; 4*(-Mmax)+1 .. 4*(Mmax)) {
		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