結果

問題 No.1815 K色問題
ユーザー okkuukenkenokkuukenken
提出日時 2022-01-12 17:24:33
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 4,275 bytes
コンパイル時間 6,839 ms
コンパイル使用メモリ 338,660 KB
実行使用メモリ 13,036 KB
最終ジャッジ日時 2024-03-13 11:30:06
合計ジャッジ時間 10,599 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
6,744 KB
testcase_01 AC 36 ms
6,676 KB
testcase_02 AC 37 ms
6,744 KB
testcase_03 AC 37 ms
6,676 KB
testcase_04 AC 37 ms
6,676 KB
testcase_05 AC 36 ms
6,744 KB
testcase_06 TLE -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

//Source.cpp
//いつもの
#ifdef LOCAL
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<list>
#include<algorithm>
#include<numeric>
#include<cmath>
#include<climits>
#include<iomanip>
#include<cctype>
#include<sstream>
#include<regex>
#include<bitset>
#include<random>
#include<complex>
#include<cassert>
#else
#include<bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#ifdef ONLINE_JUDGE
#include<atcoder/all>
using namespace atcoder;
#else
#define gcd __gcd
#define lcm __detail::__lcm
#endif
#endif
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#ifdef LOCAL
/*
#include<atcoder/all>
using namespace atcoder;
//*/
unsigned popcount(unsigned x){
	return __popcnt(x);
}
unsigned popcountll(ull x){
	return __popcnt64(x);
}
unsigned parity(unsigned x){
	return popcount(x)%2;
}
unsigned parityll(ull x){
	return popcountll(x)%2;
}
unsigned clz(unsigned x){
	if(x==0)
		throw;
	unsigned cnt=__lzcnt(x);
	return cnt;
}
unsigned clzll(ull x){
	if(x==0)
		throw;
	unsigned cnt=__lzcnt64(x);
	return cnt;
}
unsigned ctz(unsigned x){
	if(x==0)
		throw;
	x&=~x+1;
	unsigned cnt=0;
	if(x&0xffff0000)
		cnt|=16;
	if(x&0xff00ff00)
		cnt|=8;
	if(x&0xf0f0f0f0)
		cnt|=4;
	if(x&0xcccccccc)
		cnt|=2;
	if(x&0xaaaaaaaa)
		cnt|=1;
	return cnt;
}
unsigned ctzll(ull x){
	if(x==0)
		throw;
	x&=~x+1;
	unsigned cnt=0;
	if(x&0xffffffff00000000)
		cnt|=32;
	if(x&0xffff0000ffff0000)
		cnt|=16;
	if(x&0xff00ff00ff00ff00)
		cnt|=8;
	if(x&0xf0f0f0f0f0f0f0f0)
		cnt|=4;
	if(x&0xcccccccccccccccc)
		cnt|=2;
	if(x&0xaaaaaaaaaaaaaaaa)
		cnt|=1;
	return cnt;
}
unsigned ffs(unsigned x){
	if(x==0)
		return 0;
	return ctz(x)+1;
}
unsigned ffsll(ull x){
	if(x==0)
		return 0;
	return ctzll(x)+1;
}
#define __builtin_popcount popcount
#define __builtin_popcountll popcountll
#define __builtin_parity parity
#define __builtin_parityll parityll
#define __builtin_clz clz
#define __builtin_clzll clzll
#define __builtin_ctz ctz
#define __builtin_ctzll ctzll
#define __builtin_ffs ffs
#define __builtin_ffsll ffsll
#endif
constexpr int mod=1e9+7;
constexpr int Mod=998244353;
constexpr int inf=mod;
constexpr ll linf=(ll)mod*mod;
struct fastio{
	fastio(){
		cin.tie(0);
		ios::sync_with_stdio(0);
		cout<<fixed<<setprecision(20);
	};
}fio;
template<class T>
bool chmax(T&a,const T&b){
	if(a<b){
		a=b;
		return 1;
	}
	return 0;
}
template<class T>
bool chmin(T&a,const T&b){
	if(a>b){
		a=b;
		return 1;
	}
	return 0;
}
int mypow(ll x,ll n){
	ll res=1;
	while(n){
		if(n&1)
			(res*=x)%=mod;
		(x*=x)%=mod;
		n>>=1;
	}
	return res;
}
int inv(int n){
	return mypow(n,mod-2);
}
ll fact[200001],facinv[200001];
int comb(int n,int k){
	return fact[n]*facinv[k]%mod*facinv[n-k]%mod;
}
typedef vector<ll>vec;
typedef vector<vec>mat;
mat mul(mat a,mat b){
	mat c(a.size(),vec(b[0].size()));
	for(int i=0;i<a.size();i++)
		for(int j=0;j<b[0].size();j++)
			for(int k=0;k<b.size();k++)
				(c[i][j]+=a[i][k]*b[k][j])%=mod;
	return c;
}
mat pow_mat(mat a,ll n){
	mat b(a.size(),vec(a.size()));
	for(int i=0;i<a.size();i++)
		b[i][i]=1;
	while(n){
		if(n&1)
			b=mul(b,a);
		a=mul(a,a);
		n>>=1;
	}
	return b;
}
int main(){
	fact[0]=1;
	for(int i=1;i<=200000;i++)
		fact[i]=fact[i-1]*i%mod;
	for(int i=0;i<=200000;i++)
		facinv[i]=inv(fact[i]);
	int n,k;
	ll m;
	cin>>n>>m>>k;
	int ans=0;
	for(ll i=1;i<=k;i++){
		mat a,b,c;
		switch(n){
		case 1:
			a.assign(1,vec(1));
			b.assign(1,vec(1));
			c.assign(1,vec(1));
			a[0][0]=1;
			b[0][0]=i-1;
			c[0][0]=i;
			break;
		case 2:
			a.assign(1,vec(1));
			b.assign(1,vec(1));
			c.assign(1,vec(1));
			a[0][0]=1;
			b[0][0]=(i*i-3*i+3)%mod;
			c[0][0]=(i*i-i)%mod;
			break;
		case 3:
			a.assign(1,vec(2));
			b.assign(2,vec(2));
			c.assign(2,vec(1));
			a[0][0]=1;
			a[0][1]=1;
			b[0][0]=(i*i*i-i*i*6+i*14-13)%mod;
			b[0][1]=(i*i*i-i*i*6+i*13-10)%mod;
			b[1][0]=(i*i-i*4+5)%mod;
			b[1][1]=(i*i-i*3+3)%mod;
			c[0][0]=(i*i*i-i*i*3+i*2)%mod;
			c[1][0]=(i*i-i)%mod;
			break;
		}
		ll tmp=mul(a,mul(pow_mat(b,m-1),c))[0][0];
		(tmp*=comb(k,i))%=mod;
		if((k-i)%2==1)
			tmp=(-tmp+mod)%mod;
		(ans+=tmp)%=mod;
	}
	cout<<ans<<endl;
}
0