結果
問題 | No.1879 How many matchings? |
ユーザー | shotoyoo |
提出日時 | 2022-01-13 00:13:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 55 ms / 2,000 ms |
コード長 | 1,987 bytes |
コンパイル時間 | 288 ms |
コンパイル使用メモリ | 82,336 KB |
実行使用メモリ | 64,132 KB |
最終ジャッジ日時 | 2024-04-27 15:01:57 |
合計ジャッジ時間 | 1,699 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 43 ms
59,036 KB |
testcase_01 | AC | 40 ms
53,292 KB |
testcase_02 | AC | 46 ms
59,572 KB |
testcase_03 | AC | 42 ms
52,868 KB |
testcase_04 | AC | 48 ms
60,384 KB |
testcase_05 | AC | 41 ms
54,184 KB |
testcase_06 | AC | 47 ms
60,104 KB |
testcase_07 | AC | 46 ms
52,956 KB |
testcase_08 | AC | 47 ms
60,192 KB |
testcase_09 | AC | 50 ms
62,780 KB |
testcase_10 | AC | 54 ms
64,080 KB |
testcase_11 | AC | 54 ms
63,692 KB |
testcase_12 | AC | 53 ms
64,132 KB |
testcase_13 | AC | 51 ms
62,492 KB |
testcase_14 | AC | 55 ms
63,876 KB |
ソースコード
import sys input = lambda : sys.stdin.readline().rstrip() write = lambda x: sys.stdout.write(x+"\n"); writef = lambda x: print("{:.12f}".format(x)) debug = lambda x: sys.stderr.write(x+"\n") YES="Yes"; NO="No"; pans = lambda v: print(YES if v else NO) LI = lambda : list(map(int, input().split())) # sys.setrecursionlimit(3*10**5+10) ### 行列積 matrix multiplication ### 繰り返し2乗法 kurikae def mul(a,b): """行列a,bの積 aかbがNone のとき、単位行列として扱う """ if a is None: return b elif b is None: return a n,m = len(a), len(a[0]) k,l = len(b), len(b[0]) # k==m out = [[0]*l for _ in range(n)] for i in range(n): for j in range(l): for p in range(m): out[i][j] += a[i][p]*b[p][j]%M if out[i][j]>M: out[i][j] -= M return out def mul2(m,a): """行列と配列の積 m : None のとき単位行列扱い """ if m is None: return a k,l = len(m), len(m[0]) # ll = len(a) ans = [0]*k for i in range(k): for j in range(l): ans[i] += m[i][j] * a[j] % M if ans[i]>M: ans[i] -= M return ans def mulk(m, k): """a^kを求める """ if k==0: return None ans = None tmp = m while k>0: if k&1: ans = mul(ans, tmp) tmp = mul(tmp, tmp) k = k>>1 return ans M = 10**9+7 n = int(input()) a = [[0]*6 for _ in range(6)] for i in range(4): a[i][i+2] = 1 a[4][1] = a[4][2] = a[5][4] = 1 if n%2==0: b = [1,0,1,1,1,0] ak = mulk(a, n) res = mul2(ak, b) ans = res[0] else: aa = [[0]*12 for _ in range(12)] for i in range(6): for j in range(6): aa[i+6][j+6] = a[i][j] aa[i][j] = a[i][j] aa[10][3] = aa[10][4] = 1 b = [1,0,1,1,1,0, 0,0,1,0,0,1] ak = mulk(aa, n) res = mul2(ak, b) ans = res[6] print(ans%M)