結果
問題 | No.767 配られたジャパリまん |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
# 問題の首座として、通れない、としたときにどうなるか、を高速で求めたい。# 通れないは難しいから、通るものを数えて、全体から引く# 全体から引くときに、各々引いて、,,,とやるとかぶるから包除原理import sysinput = sys.stdin.buffer.readlinemod = 10 ** 8 + 7h, 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 + 5bikkuri = [0] * Nbikkuri[0] = 1gyaku = [0] * Nfor i in range(1, N):bikkuri[i] = (i * bikkuri[i - 1]) % modgyaku[N - 1] = pow(bikkuri[N - 1], mod - 2, mod)for i in range(N)[::-1]:gyaku[i - 1] = (gyaku[i] * i) % moddef comb(n, r):if r < 0 or n - r < 0:return 0return bikkuri[n] * gyaku[r] % mod * gyaku[n - r] % modpopcount = [0] * (1 << k)for i in range(1 << k):popcount[i] = popcount[i // 2] + i % 2memo = [0] * (1 << k)for i in range(1 << k):temp = 1kouho = []for j in range(k):if (i >> j) & 1:kouho.append(AB[j])kouho.sort()px, py = 0, 0for nx, ny in kouho:dx = nx - pxdy = ny - pytemp *= comb(dx + dy, dy)temp %= modpx, py = nx, nynx, ny = h, wdx = nx - pxdy = ny - pykeisu = 1 if popcount[i] % 2 else -1temp *= keisu * comb(dx + dy, dy)temp %= modmemo[i] = temptotal = 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 &= ifor 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)