結果

問題 No.767 配られたジャパリまん
ユーザー nephrologist
提出日時 2022-03-23 23:22:19
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,993 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 104,832 KB
最終ジャッジ日時 2024-10-12 02:49:06
合計ジャッジ時間 5,653 ms
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 6
other AC * 14 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#
#
# ,,,
import sys
input = sys.stdin.buffer.readline
mod = 10 ** 8 + 7
h, w, k = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(k)]
# AB.sort(key=lambda x: [x[1], x[2]])
# idx = [i for i, _, __ in AB]
N = h + w + 100 + 5
bikkuri = [0] * N
bikkuri[0] = 1
gyaku = [0] * N
for i in range(1, N):
bikkuri[i] = (i * bikkuri[i - 1]) % mod
gyaku[N - 1] = pow(bikkuri[N - 1], mod - 2, mod)
for i in range(N)[::-1]:
gyaku[i - 1] = (gyaku[i] * i) % mod
def comb(n, r):
if r < 0 or n - r < 0:
return 0
return bikkuri[n] * gyaku[r] % mod * gyaku[n - r] % mod
popcount = [0] * (1 << k)
for i in range(1 << k):
popcount[i] = popcount[i // 2] + i % 2
memo = [0] * (1 << k)
for i in range(1 << k):
temp = 1
kouho = []
for j in range(k):
if (i >> j) & 1:
kouho.append(AB[j])
kouho.sort()
px, py = 0, 0
for nx, ny in kouho:
dx = nx - px
dy = ny - py
temp *= comb(dx + dy, dy)
temp %= mod
px, py = nx, ny
nx, ny = h, w
dx = nx - px
dy = ny - py
keisu = 1 if popcount[i] % 2 else -1
temp *= keisu * comb(dx + dy, dy)
temp %= mod
memo[i] = temp
total = comb(h + w, w)
ans = memo[:]
# for i in range(1 << k):
# j = i
# while j:
# # print("i,j", i, j)
# keisu = 1 if popcount[j] % 2 else -1
# ans[i] += keisu * memo[j]
# ans[i] %= mod
# # print(keisu * memo[j])
# j -= 1
# j &= i
for i in range(k):
for j in range(1 << k):
if (j >> i) & 1:
ans[j] += ans[j ^ (1 << i)]
ans[j] %= mod
# ans = [total - a for a in ans]
for a in ans:
print(-a % mod)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0