結果
問題 | No.767 配られたジャパリまん |
ユーザー |
![]() |
提出日時 | 2021-08-04 04:34:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 734 ms / 2,000 ms |
コード長 | 2,085 bytes |
コンパイル時間 | 158 ms |
コンパイル使用メモリ | 82,292 KB |
実行使用メモリ | 137,280 KB |
最終ジャッジ日時 | 2024-09-16 15:00:00 |
合計ジャッジ時間 | 3,561 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 15 |
ソースコード
import sysdef I(): return int(sys.stdin.readline().rstrip())def MI(): return map(int,sys.stdin.readline().rstrip().split())def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))def LI2(): return list(map(int,sys.stdin.readline().rstrip()))def S(): return sys.stdin.readline().rstrip()def LS(): return list(sys.stdin.readline().rstrip().split())def LS2(): return list(sys.stdin.readline().rstrip())H,W,k = MI()mod = 10**8+7friends = []for _ in range(k):a,b = MI()friends.append((W+1)*a+b)fac = [1]for i in range(1,H+W+1):fac.append((fac[-1]*i) % mod)fac_inv = [0]*(H+W+1)f = pow(fac[-1],mod-2,mod)for i in range(H+W,-1,-1):fac_inv[i] = ff *= if %= moddef comb(n,r):return fac[n] * fac_inv[r] % mod * fac_inv[n-r] % modK = 1 << kF = [0]*Kfor i in range(K):X = [0]for j in range(k):if not (i >> j) & 1:X.append(friends[j])X.sort()X.append((W+1)*H+W)f = 1for j in range(len(X)-1):a0,b0 = divmod(X[j],W+1)a1,b1 = divmod(X[j+1],W+1)if a0 > a1 or b0 > b1:breakf *= comb((a1-a0)+(b1-b0),a1-a0)f %= modelse:F[i] = fdef mobius_transform(F,n):# res[i] = (iを含む集合jに対する (-1)^(#j-#i)F[j] の和)N = 1 << nres = F[:]for i in range(n):k = 1 << ifor j in range(N):if not j & k:res[j] -= res[j^k]res[j] %= modreturn resG = mobius_transform(F,k)[::-1]def bit_count(n):c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)return cfor i in range(K):if bit_count(i) % 2 == 1:G[i] = (-G[i]) % modprint(*G,sep='\n')