結果
問題 | No.1879 How many matchings? |
ユーザー |
|
提出日時 | 2022-01-15 19:17:18 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 54 ms / 2,000 ms |
コード長 | 2,007 bytes |
コンパイル時間 | 155 ms |
コンパイル使用メモリ | 82,104 KB |
実行使用メモリ | 63,484 KB |
最終ジャッジ日時 | 2024-11-21 22:28:08 |
合計ジャッジ時間 | 1,675 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 15 |
ソースコード
import sysinput = 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乗法 kurikaedef mul(a,b):"""行列a,bの積aかbがNone のとき、単位行列として扱う"""if a is None:return belif b is None:return an,m = len(a), len(a[0])k,l = len(b), len(b[0])# k==mout = [[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]%Mif out[i][j]>M:out[i][j] -= Mreturn outdef mul2(m,a):"""行列と配列の積m : None のとき単位行列扱い"""if m is None:return ak,l = len(m), len(m[0])# ll = len(a)ans = [0]*kfor i in range(k):for j in range(l):ans[i] += m[i][j] * a[j] % Mif ans[i]>M:ans[i] -= Mreturn ansdef mulk(m, k):"""a^kを求める"""if k==0:return Noneans = Nonetmp = mwhile k>0:if k&1:ans = mul(ans, tmp)tmp = mul(tmp, tmp)k = k>>1return ansM = 10**9+7n = int(input())assert 1<=n<=10**18a = [[0]*6 for _ in range(6)]for i in range(4):a[i][i+2] = 1a[4][1] = a[4][2] = a[5][4] = 1if 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] = 1b = [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)