結果
問題 | No.767 配られたジャパリまん |
ユーザー | ikd |
提出日時 | 2018-12-25 16:37:37 |
言語 | Nim (2.0.2) |
結果 |
AC
|
実行時間 | 1,746 ms / 2,000 ms |
コード長 | 1,737 bytes |
コンパイル時間 | 3,679 ms |
コンパイル使用メモリ | 66,832 KB |
実行使用メモリ | 18,280 KB |
最終ジャッジ日時 | 2024-07-01 06:16:12 |
合計ジャッジ時間 | 7,595 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 5 ms
6,940 KB |
testcase_05 | AC | 140 ms
8,064 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 14 ms
6,944 KB |
testcase_10 | AC | 74 ms
6,940 KB |
testcase_11 | AC | 29 ms
6,944 KB |
testcase_12 | AC | 22 ms
6,940 KB |
testcase_13 | AC | 70 ms
6,940 KB |
testcase_14 | AC | 31 ms
8,064 KB |
testcase_15 | AC | 34 ms
8,064 KB |
testcase_16 | AC | 25 ms
6,940 KB |
testcase_17 | AC | 12 ms
6,944 KB |
testcase_18 | AC | 15 ms
6,944 KB |
testcase_19 | AC | 38 ms
8,064 KB |
testcase_20 | AC | 1,746 ms
18,280 KB |
ソースコード
import strutils, sequtils, algorithm proc popcount[T: int64|int](a: T): cint {.importc: "__builtin_popcountl", nodecl, nosideeffect.} const MOD = 1_000_000_00+7 proc powmod(b, e: int64): int64 = if e==0: result = 1 elif e==1: result = b elif e mod 2 == 0: result = powmod(b*b mod MOD, e div 2) else: result = b*powmod(b, e-1) mod MOD var fac: seq[int64] inv: seq[int64] proc make(n: int) = fac = @[1'i64] inv = @[1'i64] for i in 1..<n: fac.add(fac[i-1]*i mod MOD) inv.add(powmod(fac[i], MOD-2)) proc cmb(n, r: int): int64 = if r<0 or n<r: result = 0 else: result = fac[n]*inv[r] mod MOD result = result*inv[n-r] mod MOD proc main() = let hwk = stdin.readLine.split.map(parseInt) (h, w, k) = (hwk[0], hwk[1], hwk[2]) ab = (0..<k).mapIt(stdin.readLine.split.map(parseInt)) make(h+w+1) var abi = newSeqWith(k, newSeq[int]()) for i in 0..<k: abi[i] = @[ab[i][0], ab[i][1], i] abi.sort do (p, q: seq[int])->int: result = cmp(p[0], q[0]) if result==0: result = cmp(p[1], q[1]) var dp = newSeqWith(1 shl k, 1'i64) for bits in 0..<(1 shl k): var cur_y = 0 cur_x = 0 for p in abi: if (bits and (1 shl p[2]))>0: let dy = p[0]-cur_y dx = p[1]-cur_x dp[bits] = dp[bits]*cmb(dy+dx, dy) mod MOD cur_y = p[0] cur_x = p[1] dp[bits] = dp[bits]*cmb((h-cur_y)+(w-cur_x), h-cur_y) mod MOD for i in 0..<k: for bits in 0..<(1 shl k): if (bits and (1 shl i))==0: dp[bits xor (1 shl i)] = (dp[bits xor (1 shl i)]+(MOD-dp[ bits])) mod MOD for bits, x in dp: if popcount(bits) mod 2 == 0: echo x else: echo MOD-x main()