結果

問題 No.3033 エルハートの数え上げ
ユーザー dp_ijk
提出日時 2025-02-21 22:16:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 481 ms / 2,000 ms
コード長 1,444 bytes
コンパイル時間 238 ms
コンパイル使用メモリ 82,240 KB
実行使用メモリ 90,404 KB
最終ジャッジ日時 2025-02-21 22:16:23
合計ジャッジ時間 8,498 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Lagrange:
   def __init__(self, X, Y):
      from fractions import Fraction

      assert len(X) == len(Y)
      assert len(set(X)) == len(X)
      N = len(X)

      self.C = C = []
      for i in range(N):
         res = 1
         for j in range(N):
            if i == j:
               continue
            res *= X[i] - X[j]
         c = Fraction(Y[i], res)
         C.append(c)

      self.X, self.Y = X, Y
      self.d = {x: y for x, y in zip(X, Y)}

   def __call__(self, x):
      from fractions import Fraction
      res = self.d.get(x)
      if res is not None:
         return res
      base = 1
      for a in self.X:
         base *= x-a
      res = 0
      for a, c in zip(self.X, self.C):
         res += Fraction(base, x-a) * c
      if res == int(res):
         return int(res)
      return res

def is_in(x,y,z,a,b,c,d):
   return a*x+b*y+c*z+d >= 0

MOD = 998_244_353
N, M = map(int, input().split())

ABCD = []
for _ in range(M):
   a, b, c, d = map(int, input().split())
   ABCD.append((a, b, c, d))


def naive(N):
   C = 15
   res = 0
   for x in range(-C*N, C*N + 1):
      for y in range(-C*N, C*N + 1):
         for z in range(-C*N, C*N + 1):
            for a, b, c, d in ABCD:
               if not is_in(x, y, z, a, b, c, d*N):
                  break
            else:
               res += 1
   return res


d = 3
X = [0, 1, 2, 3]
L = Lagrange(X, list(map(naive, X)))

ans = (-1)**d * L(-N)
print(ans%MOD)
0