結果

問題 No.1815 K色問題
ユーザー okkuukenken
提出日時 2022-01-10 04:42:29
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 166 ms / 2,000 ms
コード長 1,839 bytes
コンパイル時間 2,723 ms
コンパイル使用メモリ 247,392 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-09-29 22:36:21
合計ジャッジ時間 3,895 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
long long fact[200001],invfact[200001];
int main(){
	int n,k;
	long long m;
	cin>>n>>m>>k;
	fact[0]=1;
	for(int i=1;i<=k;i++)
		fact[i]=fact[i-1]*i%mod;
	for(int i=0;i<=k;i++){
		long long a=fact[i];
		long long mm=mod-2;
		long long b=1;
		while(mm){
			if(mm&1)
				(b*=a)%=mod;
			(a*=a)%=mod;
			mm>>=1;
		}
		invfact[i]=b;
	}
	int ans=0;
	for(long long i=1;i<=k;i++){
		long long tmp=0;
		if(n==1){
			long long a=i-1;
			long long x=i;
			long long mm=m-1;
			long long b=1;
			while(mm){
				if(mm&1)
					(b*=a)%=mod;
				(a*=a)%=mod;
				mm>>=1;
			}
			tmp=b*x%mod;
		}
		if(n==2){
			long long a=(i*i-3*i+3)%mod;
			long long x=(i*i-i)%mod;
			long long mm=m-1;
			long long b=1;
			while(mm){
				if(mm&1)
					(b*=a)%=mod;
				(a*=a)%=mod;
				mm>>=1;
			}
			tmp=b*x%mod;
		}
		if(n==3){
			long long a00=(i*i*i-i*i*6+i*14-13)%mod;
			long long a01=(i*i*i-i*i*6+i*13-10)%mod;
			long long a10=(i*i-i*4+5)%mod;
			long long a11=(i*i-i*3+3)%mod;
			long long x=(i*i*i-i*i*3+i*2)%mod;
			long long y=(i*i-i)%mod;
			long long mm=m-1;
			long long b00=1,b01=0,b10=0,b11=1;
			while(mm){
				if(mm&1){
					long long bb00=(b00*a00+b01*a10)%mod;
					long long bb01=(b00*a01+b01*a11)%mod;
					long long bb10=(b10*a00+b11*a10)%mod;
					long long bb11=(b10*a01+b11*a11)%mod;
					b00=bb00;
					b01=bb01;
					b10=bb10;
					b11=bb11;
				}
				long long aa00=(a00*a00+a01*a10)%mod;
				long long aa01=(a00*a01+a01*a11)%mod;
				long long aa10=(a10*a00+a11*a10)%mod;
				long long aa11=(a10*a01+a11*a11)%mod;
				a00=aa00;
				a01=aa01;
				a10=aa10;
				a11=aa11;
				mm>>=1;
			}
			tmp=(b00*x+b01*y+b10*x+b11*y)%mod;
		}
		(tmp*=fact[k]*invfact[i]%mod*invfact[k-i]%mod)%=mod;
		if((k-i)%2==1)
			tmp=(-tmp+mod)%mod;
		(ans+=tmp)%=mod;
	}
	cout<<ans<<endl;
}
0