結果

問題 No.1756 Rider's Triangle
ユーザー chineristACchineristAC
提出日時 2021-11-20 16:49:42
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 74 ms / 2,000 ms
コード長 2,066 bytes
コンパイル時間 342 ms
コンパイル使用メモリ 82,456 KB
実行使用メモリ 79,040 KB
最終ジャッジ日時 2024-06-11 18:50:42
合計ジャッジ時間 3,161 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 73 ms
78,892 KB
testcase_01 AC 53 ms
67,632 KB
testcase_02 AC 54 ms
68,244 KB
testcase_03 AC 72 ms
77,352 KB
testcase_04 AC 55 ms
68,540 KB
testcase_05 AC 52 ms
68,720 KB
testcase_06 AC 53 ms
67,912 KB
testcase_07 AC 53 ms
68,620 KB
testcase_08 AC 71 ms
77,100 KB
testcase_09 AC 71 ms
77,076 KB
testcase_10 AC 72 ms
77,380 KB
testcase_11 AC 71 ms
77,348 KB
testcase_12 AC 73 ms
77,352 KB
testcase_13 AC 73 ms
78,220 KB
testcase_14 AC 72 ms
77,160 KB
testcase_15 AC 72 ms
77,096 KB
testcase_16 AC 71 ms
77,132 KB
testcase_17 AC 72 ms
77,248 KB
testcase_18 AC 72 ms
78,492 KB
testcase_19 AC 71 ms
77,320 KB
testcase_20 AC 71 ms
77,124 KB
testcase_21 AC 71 ms
78,196 KB
testcase_22 AC 71 ms
78,252 KB
testcase_23 AC 71 ms
79,040 KB
testcase_24 AC 72 ms
78,428 KB
testcase_25 AC 72 ms
77,304 KB
testcase_26 AC 72 ms
77,940 KB
testcase_27 AC 73 ms
78,604 KB
testcase_28 AC 74 ms
77,512 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

N = 2*10**5
mod = 998244353
g1 = [1]*(N+1) # 元テーブル
g2 = [1]*(N+1) #逆元テーブル
inverse = [1]*(N+1) #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1[i]=( ( g1[i-1] * i ) % mod )
    inverse[i]=( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2[i]=( (g2[i-1] * inverse[i]) % mod )
inverse[0]=0

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return (g1[n] * g2[r] % mod) * g2[n-r] % mod



import sys,random,bisect
from collections import deque,defaultdict
from heapq import heapify,heappop,heappush
from itertools import permutations
from math import log,gcd

input = lambda :sys.stdin.readline()
mi = lambda :map(int,input().split())
li = lambda :list(mi())

a,b,N = mi()

if abs(a)==abs(b) or a*b==0:
    exit(print(0))



L = list(permutations([i for i in range(4)]))
R = list(permutations([i for i in range(3)]))
coef = [(a,b),(b,a),(a,-b),(b,-a)]

A,B = a//gcd(a,b),b//gcd(a,b)
if (A**2 + B**2)&1:
    base = [(A**2+B**2),2*A*B,A**2-B**2]
else:
    base = [(A**2+B**2)//2,A*B,(A**2-B**2)//2]

res = 0
for p in L:
    for q in R:
        for bit in range(8):
            x,y = 0,0
            mx,my = 0,0
            Mx,My = 0,0

            path = [(0,0)]

            for i in range(3):
                if bit>>i & 1:
                    nx,ny = x + coef[p[i]][0] * base[q[i]], y + coef[p[i]][1] * base[q[i]]
                    mx,my = min(mx,nx),min(my,ny)
                    Mx,My = max(Mx,nx),max(My,ny)
                    path.append((nx,ny))
                    x,y = nx,ny
                else:
                    nx,ny = x - coef[p[i]][0] * base[q[i]], y - coef[p[i]][1] * base[q[i]]
                    mx,my = min(mx,nx),min(my,ny)
                    Mx,My = max(Mx,nx),max(My,ny)
                    path.append((nx,ny))
                    x,y = nx,ny
            if x==0 and y==0:
                
                W = Mx-mx
                H = My-my
                if W <= N and H <= N:
                    res += (N-H) * (N-W)


res //= 6
print(res % 998244353)
0