#959502 (PyPy3) No.1815 K色問題

提出ソース

結果

問題	No.1815 K色問題
ユーザー	👑 p-adic
提出日時	2024-03-13 09:56:27
言語	PyPy3 (7.3.15)
結果	TLE
実行時間	-
コード長	7,277 bytes
コンパイル時間	787 ms
コンパイル使用メモリ	82,156 KB
実行使用メモリ	142,440 KB
最終ジャッジ日時	2024-09-29 22:50:13
合計ジャッジ時間	4,634 ms
ジャッジサーバーID （参考情報）	judge3 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	43 ms 58,880 KB
testcase_01	AC	41 ms 53,760 KB
testcase_02	AC	46 ms 54,708 KB
testcase_03	AC	39 ms 54,272 KB
testcase_04	AC	38 ms 54,144 KB
testcase_05	AC	38 ms 54,144 KB
testcase_06	AC	353 ms 142,440 KB
testcase_07	AC	175 ms 91,520 KB
testcase_08	TLE	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

Q=10**9+7
class ModB:
	B = Q
	length_max = 10**6 #ユーザー定義
	inverse=None
	factorial=None
	factorial_inverse=None
	def SetModulo(B):
		ModB.B = int(B)
		inverse = [None,ModB(1)]
		factorial = [ModB(1)]
		factorial_inverse = [ModB(1)]

	def __init__(self,val,valid = False):
		self.val = int(val)
		if not valid:self.val %= ModB.B
	def copy(self):
		return ModB(self.val,True)

	def __eq__(self,x):
		return x==self.val
	def __ne__(self,other):
		return not( self == other )

	def __add__(self,x):
		val = self.val + x #__radd__を使用
		if val >= ModB.B:val -= ModB.B
		return ModB(val,True)
	def __iadd__(self,other):
		self = self + other
		return self

	def __sub__(self,x):
		val = self.val - x #__rsub__を使用
		if val < 0:val += ModB.B
		return ModB(val,True)
	def __isub__(self,other):
		self = self - other
		return self
	def __neg__(self):
		return ModB(ModB.B - self.val if self.val else 0,True)

	def __mul__(self,x):
		val = self.val * x % ModB.B #__mod__を使用
		return ModB(val,True)
	def __rmul__(self,x):
		return ModB(x * self.val)
	def __imul__(self,x):
		self = self * x
		return self

	def __pow__(self,n): #n>=0の場合のみサポート
		answer = ModB(1)
		power = self.copy()
		while n > 0:
			if n&1:answer *= power
			power *= power
			n >>= 1
		return answer
	def __xor__(self,n): #Bが素数かつval!=0、またはn>=0の場合のみサポート
		return self ** ( ( n * (2 - ModB.B) )if n < 0 else n )

	def Inverse(n): #Bが素数の場合のみサポート
		if n < ModB.length_max:
			while len(ModB.inverse) <= n:ModB.inverse+=[ModB(ModB.B - ModB.inverse[ModB.B % len(ModB.inverse)].val * ( ModB.B // len(ModB.inverse) ) % ModB.B,True)]
			return ModB.inverse[n]
		else:return ModB(n) ** ( ModB.B - 2 )
	def __rtruediv__(self,x):
		return x * ModB.Inverse(self.val)
	def __itruediv__(self,other):
		self *= ModB.Inverse(other.val)
		return self

	def Factorial(n):
		while len(ModB.factorial) <= n:ModB.factorial+=[ModB.factorial[-1] * len(ModB.factorial)]
		return ModB.factorial[n]
	def FactorialInverse(n): #Bが素数の場合のみサポート
		while len(ModB.factorial_inverse) <= n:ModB.factorial_inverse+=[ModB.factorial_inverse[-1] * ModB.Inverse( len(ModB.factorial_inverse) )]
		return ModB.factorial_inverse[n]
	def Combination(n,m): #Bが素数の場合のみサポート
		return ModB.Factorial(n) * ModB.FactorialInverse(m) * ModB.FactorialInverse(n-m)if 0<=m<=n else ModB(0)

	#private:
	def __radd__(self,x): #__add__オーバーロード用
		return x + self.val
	def __rsub__(self,x): #__sub__オーバーロード用
		return x - self.val	
	def __mod__(self,x): #__mul__オーバーロード用
		return self.val
ModB.inverse = [None,ModB(1)]
ModB.factorial = [ModB(1)]
ModB.factorial_inverse = [ModB(1)]

class TwoByTwoMatrix:
	zero=None
	one=None

	def __init__(self,M00,M01,M10,M11):
		self.M00 = M00
		self.M01 = M01
		self.M10 = M10
		self.M11 = M11
	def copy(self):
		return self.__class__(self.M00,self.M01,self.M10,self.M11)

	def __eq__(self,other):
		return self.M00 == other.M00 and self.M01 == other.M01 and self.M10 == other.M10 and self.M11 == other.M11
	def __ne__(self,other):
		return not( self == other )

	def __iadd__(self,other):
		self.M00 += other.M00
		self.M01 += other.M01
		self.M10 += other.M10
		self.M11 += other.M11
		return self
	def __add__(self,other):
		M = self.copy()
		M += other
		return M

	def __isub__(self,other):
		self.M00 -= other.M00
		self.M01 -= other.M01
		self.M10 -= other.M10
		self.M11 -= other.M11
		return self
	def __sub__(self,other):
		M = self.copy()
		M -= other
		return M
	def __neg__(self):
		return self.__class__(-self.M00,-self.M01,-self.M10,-self.M11)

	def __mul__(self,other):
		return self.__class__(self.M00 * other.M00 + self.M01 * other.M10,self.M00 * other.M01 + self.M01 * other.M11,self.M10 * other.M00 + self.M11 * other.M10,self.M10 * other.M01 + self.M11 * other.M11)
	def __imul__(self,other):
		self.M00 , self.M01 , self.M10 , self.M11 = self.M00 * other.M00 + self.M01 * other.M10 , self.M00 * other.M01 + self.M01 * other.M11 , self.M10 * other.M00 + self.M11 * other.M10 , self.M10 * other.M01 + self.M11 * other.M11
		return self
	def ScalarMultiply(self,x):
		self.M00 *= x
		self.M01 *= x
		self.M10 *= x
		self.M11 *= x
		return self

	def det(self):
		return self.M00 * self.M11 - self.M01 * self.M10
	def tr(self):
		return self.M00 + self.M11

	def Adjugate(self):
		return self.__class__( self.M11 , - self.M01 , - self.M10 , self.M00 )
	def Inverse(self):
		return self.Adjugate().ScalarMultiply( 1 / self.det() )
		# d = self.det()
		# assert( d in [1,-1] ) # 整数係数の場合
		# return self.Adjugate().ScalarMultiply( d )
	def __truediv__(self,other):
		return self * other.Inverse()
	def __itruediv__(self,other):
		self *= other.Inverse()
		return self

	def __pow__(self,n): #n>=0の場合のみサポート
		answer = self.__class__.one.copy()
		power = self.copy()
		while n > 0:
			if n&1:answer *= power
			power.Square()
			n >>= 1
		return answer
	def __xor__(self,n):
		return self.Inverse()**(-n)if n < 0 else self ** n

	#private:
	def Square(self):
		self.M00 , self.M01 , self.M10 , self.M11 = self.M00 ** 2 + self.M01 * self.M10 , ( self.M00 + self.M11 ) * self.M01 , self.M10 * ( self.M00 + self.M11 ) , self.M10 * self.M01 + self.M11 ** 2
TwoByTwoMatrix.zero = TwoByTwoMatrix(ModB(0),ModB(0),ModB(0),ModB(0)) #ユーザー定義
TwoByTwoMatrix.one = TwoByTwoMatrix(ModB(1),ModB(0),ModB(0),ModB(1)) #ユーザー定義

class TwoByOneMatrix:
	zero=None

	def __init__(self,M0,M1):
		self.M0 = M0
		self.M1 = M1
	def copy(self):
		return self.__class__(self.M0,self.M1)

	def __eq__(self,other):
		return self.M0 == other.M0 and self.M1 == other.M1
	def __ne__(self,other):
		return not( self == other )

	def __iadd__(self,other):
		self.M0 += other.M0
		self.M1 += other.M1
		return self
	def __add__(self,other):
		M = self.copy()
		M += other
		return M

	def __isub__(self,other):
		self.M0 -= other.M0
		self.M1 -= other.M1
		return self
	def __sub__(self,other):
		M = self.copy()
		M -= other
		return M
	def __neg__(self):
		return self.__class__(-self.M0,-self.M1)

	def __rmul__(self,T):
		return self.copy().Act(T)
	def Act(self,T):
		self.M0 , self.M1 = T.M00 * self.M0 + T.M01 * self.M1 , T.M10 * self.M0 + T.M11 * self.M1
		return self
	def ScalarMultiply(self,x):
		self.M0 *= x
		self.M1 *= x
		return self
TwoByOneMatrix.zero = TwoByOneMatrix(ModB(0),ModB(0)) #ユーザー定義

R=range
N,M,K=map(int,input().split())
answer=ModB(0)
j=ModB(0)
if K<2:answer+=(N*M<2)
elif N*M<K:
	0
elif N<2:
	M=(M-1)%(Q-1)
	K-=1
	for k in R(K+1):
		d=ModB.Combination(K,k)*(j**M)
		if k&1:answer-=d
		else:answer+=d
		j+=1
	answer*=j
elif N<3:
	M=(M-1)%(Q-1)
	K-=2
	for k in R(K+1):
		d=ModB.Combination(K,k)*(((j+1)*j+1)**M)
		if k&1:answer-=d
		else:answer+=d
		j+=1
	answer*=j*(j+1)
else:
	answer_vec=TwoByOneMatrix(ModB(1),ModB(0))
	M-=1
	K-=2
	for k in R(1,K+1):
		h1=j.copy()
		j+=1
		h2=j*j+1
		h3=h2*j
		d=TwoByOneMatrix(ModB(1),j.copy())
		Transfer=TwoByTwoMatrix(h2+j,h2,h3,h3+h1)
		d.Act(Transfer**M).ScalarMultiply(ModB.Combination(K,k))
		if k&1:answer_vec-=d
		else:answer_vec+=d
	answer=(answer_vec.M0+answer_vec.M1)*(j+1)*(j+2)
if K&1:answer=-answer
print(answer.val)

yukicoder

結果

テストケース

ソースコード