結果
問題 | No.474 色塗り2 |
ユーザー |
![]() |
提出日時 | 2020-01-02 13:05:13 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,090 ms / 2,000 ms |
コード長 | 1,493 bytes |
コンパイル時間 | 444 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 257,580 KB |
最終ジャッジ日時 | 2025-02-07 00:17:29 |
合計ジャッジ時間 | 8,581 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 4 |
ソースコード
import sysread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlinesimport numpy as npN = int(readline())ABC = np.array(read().split(),np.int64)A = ABC[::3]B = ABC[1::3]C = ABC[2::3]MOD = 1 << 20# 二項係数 mod MODが必要。素因数 2 を無視して階乗を作るdef cumprod(A, MOD = MOD):L = len(A); Lsq = int(L**.5+1)A = np.resize(A, Lsq**2).reshape(Lsq,Lsq)for n in range(1,Lsq):A[:,n] *= A[:,n-1]; A[:,n] %= MODfor n in range(1,Lsq):A[n] *= A[n-1,-1]; A[n] %= MODreturn A.ravel()[:L]U = 1 << 22x = np.arange(U, dtype = np.int64); x[0] = 1n = 2while n < U:x[n::n] //= 2n *= 2fact = cumprod(x, MOD)y = np.empty_like(x); y[1:] = x[1:][::-1]y[0] = pow(int(fact[-1]), MOD-1, MOD) # inversefact_inv = cumprod(y, MOD)[::-1]def popcount_table(N):# N 未満の~~L = (N-1).bit_length()A = np.zeros(1<<L,np.int32)for i in range(L):A[1<<i:1<<(i+1)] = A[:1<<i] + 1return A[:N]popcount = popcount_table(U)"""・D = C * comb(B+C-1,B)・x = C * comb(A+D-1,A)・x mod 2が知りたい。D mod MOD が知りたい。"""D = fact[B+C-1] * fact_inv[B] * fact_inv[C-1] % MOD; D *= C; D %= MODn = popcount[B] + popcount[C-1] - popcount[B+C-1]D <<= n; D %= MODx = fact[A+D-1] * fact_inv[A] * fact_inv[D-1] % MOD; x *= C; x %= MODn = popcount[A] + popcount[D-1] - popcount[A+D-1]x <<= n; x &= 1print('\n'.join(x.astype(str)))