結果

問題 No.1756 Rider's Triangle
ユーザー chineristACchineristAC
提出日時 2021-11-20 16:49:42
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 179 ms / 2,000 ms
コード長 2,066 bytes
コンパイル時間 1,948 ms
コンパイル使用メモリ 86,908 KB
実行使用メモリ 86,312 KB
最終ジャッジ日時 2023-09-02 12:06:28
合計ジャッジ時間 8,663 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 178 ms
85,904 KB
testcase_01 AC 144 ms
82,588 KB
testcase_02 AC 145 ms
82,580 KB
testcase_03 AC 166 ms
83,612 KB
testcase_04 AC 144 ms
82,756 KB
testcase_05 AC 145 ms
83,000 KB
testcase_06 AC 148 ms
82,884 KB
testcase_07 AC 146 ms
82,956 KB
testcase_08 AC 175 ms
86,024 KB
testcase_09 AC 173 ms
86,116 KB
testcase_10 AC 174 ms
86,096 KB
testcase_11 AC 175 ms
86,092 KB
testcase_12 AC 174 ms
86,024 KB
testcase_13 AC 176 ms
85,908 KB
testcase_14 AC 170 ms
83,628 KB
testcase_15 AC 165 ms
83,880 KB
testcase_16 AC 172 ms
83,608 KB
testcase_17 AC 175 ms
86,108 KB
testcase_18 AC 178 ms
86,264 KB
testcase_19 AC 168 ms
83,832 KB
testcase_20 AC 174 ms
83,428 KB
testcase_21 AC 178 ms
86,132 KB
testcase_22 AC 172 ms
83,616 KB
testcase_23 AC 177 ms
86,272 KB
testcase_24 AC 176 ms
86,112 KB
testcase_25 AC 179 ms
86,260 KB
testcase_26 AC 175 ms
86,016 KB
testcase_27 AC 175 ms
86,124 KB
testcase_28 AC 175 ms
86,312 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