結果
問題 | No.940 ワープ ε=ε=ε=ε=ε=│;p>д<│ |
ユーザー | maspy |
提出日時 | 2019-12-03 09:07:10 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,704 bytes |
コンパイル時間 | 1,508 ms |
コンパイル使用メモリ | 11,212 KB |
実行使用メモリ | 190,784 KB |
最終ジャッジ日時 | 2023-08-18 23:37:45 |
合計ジャッジ時間 | 16,246 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 360 ms
141,532 KB |
testcase_01 | AC | 359 ms
141,316 KB |
testcase_02 | AC | 367 ms
141,672 KB |
testcase_03 | AC | 359 ms
141,396 KB |
testcase_04 | WA | - |
testcase_05 | AC | 370 ms
141,412 KB |
testcase_06 | AC | 354 ms
141,472 KB |
testcase_07 | AC | 362 ms
141,368 KB |
testcase_08 | AC | 357 ms
141,372 KB |
testcase_09 | AC | 343 ms
141,640 KB |
testcase_10 | AC | 360 ms
141,504 KB |
testcase_11 | AC | 356 ms
141,532 KB |
testcase_12 | AC | 355 ms
141,352 KB |
testcase_13 | AC | 355 ms
141,452 KB |
testcase_14 | AC | 352 ms
141,412 KB |
testcase_15 | AC | 471 ms
141,348 KB |
testcase_16 | AC | 716 ms
174,628 KB |
testcase_17 | AC | 371 ms
141,344 KB |
testcase_18 | AC | 384 ms
141,388 KB |
testcase_19 | AC | 370 ms
141,408 KB |
testcase_20 | AC | 377 ms
141,420 KB |
testcase_21 | AC | 375 ms
141,468 KB |
testcase_22 | AC | 560 ms
158,484 KB |
testcase_23 | AC | 715 ms
175,028 KB |
testcase_24 | AC | 594 ms
162,556 KB |
testcase_25 | AC | 795 ms
185,248 KB |
testcase_26 | AC | 799 ms
190,784 KB |
ソースコード
import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines import numpy as np X,Y,Z = map(int,read().split()) MOD = 10 ** 9 + 7 def cumprod(arr,MOD): L = len(arr); Lsq = int(L**.5+1) arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq) for n in range(1,Lsq): arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD for n in range(1,Lsq): arr[n] *= arr[n-1,-1]; arr[n] %= MOD return arr.ravel()[:L] def make_fact(U,MOD): x = np.arange(U,dtype=np.int64); x[0] = 1 fact = cumprod(x,MOD) x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD) fact_inv = cumprod(x,MOD)[::-1] return fact,fact_inv def make_power(a,L,MOD): B = L.bit_length() x = np.empty(1 + (1<<B),np.int64) x[0] = 1; x[1] = a for n in range(B): x[1<<n:1<<(n+1)] = x[:1<<n] * (a * x[(1<<n)-1] % MOD) % MOD return x[:L] U = 2 * 10 ** 6 + 100 fact,fact_inv = make_fact(U,MOD) power2 = make_power(2,U,MOD) power2_inv = make_power((MOD+1)//2,U,MOD) def convolve(A,B,size=32): """ 誤差回避のため8bit整数以下にしてからnp.fftを呼ぶ """ if size <= 8: LA = len(A); LB = len(B); L = LA + LB - 1 fft_len = 1 << (L.bit_length()) ifft = np.fft.irfft; fft = np.fft.rfft return ((ifft(fft(A,fft_len) * fft(B,fft_len))) + .5).astype(np.int64)[:L] % MOD size //= 2 M = 1 << size A1,A2 = np.divmod(A,M) # yukiのバージョンならあるはず B1,B2 = np.divmod(B,M) X = convolve(A1,B1,size) Y = convolve(A1+A2,B1+B2,size) Z = convolve(A2,B2,size) return ((X * (M * M % MOD)) + (Y - X - Z) * M + Z) % MOD def f(X,Y,Z): """ (2-2P/1-2P)^N * 2(1/2-2P) の x^Xy^Y の係数を返す """ N = Z + 1 U = X + Y + 100 # 分子 A = fact[N] * fact_inv[:N+1] % MOD * fact_inv[:N+1][::-1] A[1::2] *= (-1); A %= MOD A = A[:U]; A *= power2[N]; A %= MOD # 分母の逆 B = fact[N-1:N+U-1] * fact_inv[N-1] % MOD * fact_inv[:U] % MOD B *= power2[:U]; B %= MOD C = convolve(A,B)[:U] # 4 - 4P で割る C *= (MOD+1)//4; C %= MOD; np.cumsum(C,out=C); C %= MOD # 各 n に対して、P^n = (x + y - xy)^n での x^Xy^Y の係数を求める L = max(X,Y); R = X+Y x = np.zeros(R-L+1,np.int64) x = fact[L:R+1].copy() x *= fact_inv[L-Y:R-Y+1]; x %= MOD x *= fact_inv[L-X:R-X+1]; x %= MOD x *= fact_inv[0:X+Y-L+1][::-1]; x %= MOD x[(R+L+1)%2::2] *= (-1) return (x * C[L:R+1] % MOD).sum() % MOD # 3, 13, 512, 882313923 # f(1,1,0), f(1,1,1), f(10,0,0), f(31,53,6000), f(53,31,6000) # f(6000,31,53), f(6000,53,31) answer = f(X,Y,Z) print(answer)