結果
問題 | No.1879 How many matchings? |
ユーザー | Eki1009 |
提出日時 | 2022-03-18 22:44:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 47 ms / 2,000 ms |
コード長 | 527 bytes |
コンパイル時間 | 340 ms |
コンパイル使用メモリ | 82,592 KB |
実行使用メモリ | 60,760 KB |
最終ジャッジ日時 | 2024-10-03 07:39:43 |
合計ジャッジ時間 | 1,808 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 15 |
ソースコード
mod = 10**9+7 def mul(A,B): C = [0]*(len(A)+len(B)-1) for i,a in enumerate(A): for j,b in enumerate(B): C[i+j] = (C[i+j]+a*b)%mod return C def bostan_mori(P,Q,n): if n < 0: return 0 while n: X = Q.copy() for i in range(1,len(X),2): X[i] *= -1 P = mul(P,X)[n&1::2] Q = mul(Q,X)[::2] n >>= 1 return P[0] n = int(input()) P = [1] Q = [1,-1,-1] if n%2 == 0: ans = bostan_mori(P,Q,n//2) else: Q = mul(Q,Q) ans = (bostan_mori(P,Q,n//2)+bostan_mori(P,Q,n//2-1))%mod print(ans)