結果
問題 | No.767 配られたジャパリまん |
ユーザー |
![]() |
提出日時 | 2021-08-04 12:17:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,722 ms / 2,000 ms |
コード長 | 1,752 bytes |
コンパイル時間 | 323 ms |
コンパイル使用メモリ | 82,396 KB |
実行使用メモリ | 259,912 KB |
最終ジャッジ日時 | 2024-09-16 15:01:55 |
合計ジャッジ時間 | 5,041 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 15 |
ソースコード
H,W,K = map(int,input().split())L = [list(map(int,input().split())) for _ in range(K)]L = [L[i][0]*(W+1)+L[i][1] for i in range(K)]MOD = 10**8+7factorial = [1, 1]inverse = [1, 1]invere_base = [0, 1]for i in range(2, H+W + 1):factorial.append((factorial[-1] * i) % MOD)invere_base.append((-invere_base[MOD % i] * (MOD // i)) % MOD) #逆元inverse.append((inverse[-1] * invere_base[-1]) % MOD) #階乗逆元def nCr(n, r):if (r < 0 or r > n):return 0r = min(r, n - r)return factorial[n] * inverse[r] * inverse[n - r] % MODdef 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 cD = [0]*(1<<K)for i in range(1<<K):X = []for j in range(K):if i&(1<<j):X.append(L[j])X.sort()lx = len(X)a,b = 0,0ans = 1for j in range(lx):na,nb = divmod(X[j],W+1)da,db = na-a,nb-bans *= nCr(da+db,db)ans %= MODa,b = na,nbna,nb = H,Wda,db = na-a,nb-bans *= nCr(da+db,db)ans %= MODif bit_count(i)%2:ans *= -1D[i] = ans%MODdp = [D[i] for i in range(1<<K)]for j in range(K):ndp = [0]*(1<<K)for i in range(1<<K):if i&(1<<j):ndp[i] = dp[i]+dp[i&(~(1<<j))]else:ndp[i] = dp[i]ndp[i] %= MODdp = ndp[:]for i in range(1<<K):print(dp[i])