結果
問題 | No.2406 Difference of Coordinate Squared |
ユーザー |
|
提出日時 | 2023-08-04 22:45:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 163 ms / 2,000 ms |
コード長 | 2,093 bytes |
コンパイル時間 | 363 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 99,712 KB |
最終ジャッジ日時 | 2024-11-26 18:05:08 |
合計ジャッジ時間 | 8,067 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 55 |
ソースコード
import sysinput = lambda :sys.stdin.readline().rstrip()def cmb(n, r, mod):if ( r<0 or r>n ):return 0return (g1[n] * g2[r] % mod) * g2[n-r] % modmod = 998244353N = 10**6 + 10g1 = [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]=0N,M = map(int,input().split())if M == 0:res = 0"""X+Y = 0"""if N & 1 == 0:res += cmb(N,N//2,mod) * pow(inverse[2],N,mod) * 2 % modres %= modres -= cmb(N,N//2,mod) * cmb(N,N//2,mod) * pow(inverse[2],2*N,mod) % modres %= modprint(res)else:divisors = []for d in range(1,abs(M)+1):if d*d > abs(M):breakif M % d == 0:divisors.append(d)divisors.append(-d)if abs(M)//d != d:divisors.append(M//d)divisors.append(-M//d)divisors.sort()res = 0for d in divisors:p = dm = M // dtmp = 1if (N+p) & 1 == 0 and 0 <= (N+p)//2 <= N:tmp *= cmb(N,(N+p)//2,mod)tmp %= modelse:tmp = 0if (N+m) & 1 == 0 and 0 <= (N+m)//2 <= N:tmp *= cmb(N,(N+m)//2,mod)tmp %= modelse:tmp = 0res += tmpres %= modres *= pow(inverse[4],N,mod)res %= modprint(res)exit()dp = [[0]*(2*N+1) for i in range(2*N+1)]dp[0][0] = 1for _ in range(N):ndp = [[0]*(2*N+1) for i in range(2*N+1)]for i in range(-N,N+1):for j in range(-N,N+1):if not dp[i][j]:continuefor ni,nj in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:ndp[ni][nj] += dp[i][j] * inverse[4] % modndp[ni][nj] %= moddp = ndpcheck = 0for i in range(-N,N+1):for j in range(-N,N+1):if i*i-j*j == M:check += dp[i][j]check %= modprint(check)