結果

問題 No.3033 エルハートの数え上げ
コンテスト
ユーザー TKTYI
提出日時 2025-02-21 22:42:07
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 11 ms / 2,000 ms
コード長 1,195 bytes
コンパイル時間 3,835 ms
コンパイル使用メモリ 278,628 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2025-02-21 22:42:15
合計ジャッジ時間 5,198 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define all(a) begin(a),end(a)
#define sz(a) (int)(a).size()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
const ll mod=998244353;
ll pow_mod(ll a,ll n){
	a%=mod;
	ll res=1;
	while(n){
		if(n%2)res=res*a%mod;
		a=a*a%mod;n/=2;
	}
	if(res<0)res+=mod;
	return res;
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	int N,M;cin>>N>>M;
	vector<ll>A(M),B(M),C(M),D(M);
	rep(i,0,M)cin>>A[i]>>B[i]>>C[i]>>D[i];
	ll a=0,b=0,c=0,d=0;
	//f(1),f(2),f(-1),f(-2)
	rep(x,-15,16)rep(y,-15,16)rep(z,-15,16){
		bool Int=1,Cl=1;
		rep(i,0,M){
			if(A[i]*x+B[i]*y+C[i]*z+D[i]<0)Cl=0;
			if(A[i]*x+B[i]*y+C[i]*z+D[i]<=0)Int=0;
		}
		if(Int)c--;
		if(Cl)a++;
	}
	rep(x,-30,31)rep(y,-30,31)rep(z,-30,31){
		bool Int=1,Cl=1;
		rep(i,0,M){
			if(A[i]*x+B[i]*y+C[i]*z+2*D[i]<0)Cl=0;
			if(A[i]*x+B[i]*y+C[i]*z+2*D[i]<=0)Int=0;
		}
		if(Int)d--;
		if(Cl)b++;
	}
	ll p=8*a-2*b+8*c-2*d;
	ll q=8*a-b-8*c+d;
	ll r=-2*a+2*b-2*c+2*d;
	ll s=-2*a+b+2*c-d;
	ll f=p-N%mod*q%mod+N%mod*N%mod*r%mod-N%mod*N%mod*N%mod*s%mod;
	f*=-pow_mod(12,mod-2);
	f%=mod;
	if(f<0)f+=mod;
	cout<<f<<endl;
}
0