結果
問題 | No.793 うし数列 2 |
ユーザー |
👑 ![]() |
提出日時 | 2020-06-12 14:36:55 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 43 ms / 2,000 ms |
コード長 | 2,505 bytes |
コンパイル時間 | 202 ms |
コンパイル使用メモリ | 82,556 KB |
実行使用メモリ | 54,544 KB |
最終ジャッジ日時 | 2024-06-24 03:55:02 |
合計ジャッジ時間 | 2,111 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 |
ソースコード
class Modulo_Error(Exception):passclass Modulo():def __init__(self,a,n):self.a=a%nself.n=ndef __str__(self):return "{} (mod {})".format(self.a,self.n)#+,-def __pos__(self):return selfdef __neg__(self):return Modulo(-self.a,self.n)#等号,不等号def __eq__(self,other):if isinstance(other,Modulo):return (self.a==other.a) and (self.n==other.n)elif isinstance(other,int):return (self-other).a==0def __neq__(self,other):return not(self==other)#加法def __add__(self,other):if isinstance(other,Modulo):if self.n!=other.n:raise Modulo_Error("異なる法同士の演算です.")return Modulo(self.a+other.a,self.n)elif isinstance(other,int):return Modulo(self.a+other,self.n)def __radd__(self,other):if isinstance(other,int):return Modulo(self.a+other,self.n)#減法def __sub__(self,other):return self+(-other)def __rsub__(self,other):if isinstance(other,int):return -self+other#乗法def __mul__(self,other):if isinstance(other,Modulo):if self.n!=other.n:raise Modulo_Error("異なる法同士の演算です.")return Modulo(self.a*other.a,self.n)elif isinstance(other,int):return Modulo(self.a*other,self.n)def __rmul__(self,other):if isinstance(other,int):return Modulo(self.a*other,self.n)#Modulo逆数def Modulo_Inverse(self):x0, y0, x1, y1 = 1, 0, 0, 1a,b=self.a,self.nwhile b != 0:q, a, b = a // b, b, a % bx0, x1 = x1, x0 - q * x1y0, y1 = y1, y0 - q * y1if a!=1:raise Modulo_Error("{}の逆数が存在しません".format(self))else:return Modulo(x0,self.n)#除法def __truediv__(self,other):return self*other.Modulo_Inverse()#累乗def __pow__(self,m):u=abs(m)r=Modulo(1,self.n)while u>0:if u%2==1:r*=selfself*=selfu=u>>1if m>=0:return relse:return r.Modulo_Inverse()N=int(input())M=10**9+7U=Modulo(10,M)print(((4*U**N-1)/Modulo(3,M)).a)