結果
問題 | No.1126 SUM |
ユーザー |
👑 ![]() |
提出日時 | 2020-07-24 22:22:33 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 95 ms / 1,000 ms |
コード長 | 3,013 bytes |
コンパイル時間 | 189 ms |
コンパイル使用メモリ | 82,060 KB |
実行使用メモリ | 92,160 KB |
最終ジャッジ日時 | 2024-06-25 21:48:42 |
合計ジャッジ時間 | 3,235 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
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 __rtruediv__(self,other):return other*(self.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()#階乗の剰余のリストdef Factorial_Modulo_List(N,M,Inverse=False):X=[0]*(N+1)X[0]=Modulo(1,M)for i in range(1,N+1):X[i]=X[i-1]*iif Inverse:Y=[0]*(N+1)Y[-1]=1/X[-1]for j in range(N-1,-1,-1):Y[j]=Y[j+1]*(j+1)return X,Yelse:return X#-------------------------------------------------N,M=map(int,input().split())K=10**9+7F,G=Factorial_Modulo_List(M+1,K,True)print((F[M+1]*G[N+1]*G[M-N]).a)