結果

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

ソースコード

diff #
プレゼンテーションモードにする

import sys
input = lambda :sys.stdin.readline()[:-1]
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")
no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")
#######################################################################
SIZE=10**7+5; MOD=998244353 #998244353 #ここを変更する
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    fac[i] = fac[i-1]*i%MOD
finv[-1] = pow(fac[-1],MOD-2,MOD)
for i in range(SIZE-1,0,-1):
    finv[i-1] = finv[i]*i%MOD
def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0
def Lagrange_interpolation(a,t):
    n = len(a)-1
    t %= MOD
    if 0 <= t <= n: return a[t]
    rprod = [1]*(n+2)
    r = 1
    for i in range(n+2):
        rprod[n+1-i] = r
        r = r*(t-n+i)%MOD
    ans, lprod = 0, 1
    for i,ai in enumerate(a):
        bunsi = lprod*rprod[i+1]%MOD
        bunbo = finv[i]*finv[n-i]%MOD*(-1 if (n-i)%2 else 1)
        ans += bunsi*bunbo%MOD*ai%MOD
        lprod = lprod*(t-i)%MOD
    return ans%MOD
def check(p, q, k):
    return p[0] * q[0] + p[1] * q[1] + p[2] * q[2] + q[3] * k > 0
A = 15
def solve(m, k, g):
    ans = 0
    for x in range(-k*A, k*A + 1):
        for y in range(-k*A, k*A + 1):
            for z in range(-k*A, k*A + 1):
                if all(check((x, y, z), g[i], k) for i in range(m)):
                    ans += 1
    return ans
n, m = na()
g = [na() for i in range(m)]
k = 4
a = [solve(m, i, g) for i in range(1,k+1)]
# print(solve(m, n, g))
# print(*a)
print(Lagrange_interpolation(a, n-1))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0