結果
問題 | No.1846 Good Binary Matrix |
ユーザー | ygd. |
提出日時 | 2022-02-18 23:58:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 773 ms / 2,000 ms |
コード長 | 1,692 bytes |
コンパイル時間 | 343 ms |
コンパイル使用メモリ | 87,232 KB |
実行使用メモリ | 247,340 KB |
最終ジャッジ日時 | 2023-09-11 20:18:01 |
合計ジャッジ時間 | 18,215 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 320 ms
246,940 KB |
testcase_01 | AC | 332 ms
246,632 KB |
testcase_02 | AC | 330 ms
246,944 KB |
testcase_03 | AC | 318 ms
246,744 KB |
testcase_04 | AC | 327 ms
246,840 KB |
testcase_05 | AC | 311 ms
246,880 KB |
testcase_06 | AC | 297 ms
247,180 KB |
testcase_07 | AC | 297 ms
247,168 KB |
testcase_08 | AC | 312 ms
246,824 KB |
testcase_09 | AC | 292 ms
247,044 KB |
testcase_10 | AC | 298 ms
246,904 KB |
testcase_11 | AC | 295 ms
247,076 KB |
testcase_12 | AC | 304 ms
246,932 KB |
testcase_13 | AC | 306 ms
247,176 KB |
testcase_14 | AC | 309 ms
246,820 KB |
testcase_15 | AC | 308 ms
246,940 KB |
testcase_16 | AC | 724 ms
246,660 KB |
testcase_17 | AC | 765 ms
247,340 KB |
testcase_18 | AC | 709 ms
246,824 KB |
testcase_19 | AC | 773 ms
246,976 KB |
testcase_20 | AC | 756 ms
246,780 KB |
testcase_21 | AC | 340 ms
246,820 KB |
testcase_22 | AC | 362 ms
246,932 KB |
testcase_23 | AC | 317 ms
246,744 KB |
testcase_24 | AC | 322 ms
246,740 KB |
testcase_25 | AC | 649 ms
246,772 KB |
testcase_26 | AC | 559 ms
247,244 KB |
testcase_27 | AC | 339 ms
247,004 KB |
testcase_28 | AC | 380 ms
246,772 KB |
testcase_29 | AC | 462 ms
246,768 KB |
testcase_30 | AC | 688 ms
247,204 KB |
testcase_31 | AC | 623 ms
247,076 KB |
testcase_32 | AC | 717 ms
246,752 KB |
testcase_33 | AC | 744 ms
246,824 KB |
testcase_34 | AC | 329 ms
246,760 KB |
ソースコード
import sys #input = sys.stdin.readline #文字列につけてはダメ #input = sys.stdin.buffer.readline #文字列につけてはダメ #sys.setrecursionlimit(1000000) #import bisect #import itertools #import random #from heapq import heapify, heappop, heappush #from collections import defaultdict #from collections import deque #import copy #import math #from functools import lru_cache #@lru_cache(maxsize=None) MOD = pow(10,9) + 7 #MOD = 998244353 #dx = [1,0,-1,0] #dy = [0,1,0,-1] def cmb(n, r, p): if (r < 0) or (n < r): return 0 r = min(r, n - r) ret = fac[n] * finv[r] % p ret = ret * finv[n-r] % p return ret def cmb_inv(n, r, p): if (r < 0) or (n < r): return 0 r = min(r, n - r) ret = fac[n-r] * fac[r] % p ret = ret * finv[n] % p return ret def perm(n,r,p): if (r < 0) or (n < r): return 0 return fac[n]*finv[n-r]%p n = 2*pow(10,6) + 100 fac = [-1]*(n+1); fac[0] = 1; fac[1] = 1 #階乗 finv = [-1]*(n+1); finv[0] = 1; finv[1] = 1 #階乗の逆元 inv = [-1]*(n+1); inv[0] = 0; inv[1] = 1 #逆元 for i in range(2,n+1): fac[i] = fac[i-1]*i%MOD inv[i] = MOD - inv[MOD%i]*(MOD//i)%MOD finv[i] = finv[i-1]*inv[i]%MOD pow2 = [1] mx = 2*pow(10,6) + 100 for i in range(mx): temp = pow2[-1]*2%MOD pow2.append(temp) def sgn(x): if x%2 == 0: return 1 else: return - 1 def main(): H,W = map(int,input().split()) ans = 0 for i in range(H+1): #i行が0のみ x = pow2[H-i] - 1 #列に一つでも1がある決め方。"全通り - 0のみの1通り" temp = cmb(H,i,MOD) * sgn(i) * pow(x,W,MOD) %MOD ans += temp ans %= MOD print(ans) if __name__ == '__main__': main()