結果

問題 No.1756 Rider's Triangle
ユーザー chineristAC
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

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