結果

問題 No.1815 K色問題
ユーザー okkuukenkenokkuukenken
提出日時 2022-01-10 02:17:29
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 4,268 bytes
コンパイル時間 5,299 ms
コンパイル使用メモリ 281,456 KB
実行使用メモリ 6,676 KB
最終ジャッジ日時 2024-03-13 11:29:43
合計ジャッジ時間 7,096 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
6,676 KB
testcase_01 AC 37 ms
6,676 KB
testcase_02 AC 37 ms
6,676 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 AC 37 ms
6,676 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 140 ms
6,676 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 AC 65 ms
6,676 KB
testcase_12 AC 37 ms
6,676 KB
testcase_13 AC 37 ms
6,676 KB
testcase_14 AC 179 ms
6,676 KB
testcase_15 AC 199 ms
6,676 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:243:21: warning: 'tmp' may be used uninitialized [-Wmaybe-uninitialized]
  243 |                 (tmp*=comb(k,i))%=mod;
      |                  ~~~^~~~~~~~~~~
main.cpp:184:20: note: 'tmp' was declared here
  184 |                 ll tmp;
      |                    ^~~

ソースコード

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],invfact[200001];
int comb(int n,int k){
	return fact[n]*invfact[k]%mod*invfact[n-k]%mod;
}
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++)
		invfact[i]=inv(fact[i]);
	int n,k;
	ll m;
	cin>>n>>m>>k;
	int ans=0;
	for(ll i=1;i<=k;i++){
		ll tmp;
		if(n==1){
			ll a=i-1;
			ll x=i;
			ll mm=m-1;
			ll b=1;
			while(mm){
				if(mm&1)
					(b*=a)%=mod;
				(a*=a)%mod;
				mm>>=1;
			}
			tmp=b*x%mod;
		}
		if(n==2){
			ll a=(i*i-3*i+3)%mod;
			ll x=(i*i-i)%mod;
			ll mm=m-1;
			ll b=1;
			while(mm){
				if(mm&1)
					(b*=a)%=mod;
				(a*=a)%mod;
				mm>>=1;
			}
			tmp=b*x%mod;
		}
		if(n==3){
			ll a00=(i*i*i-i*i*6+i*14-13)%mod;
			ll a01=(i*i*i-i*i*6+i*13-10)%mod;
			ll a10=(i*i-i*4+5)%mod;
			ll a11=(i*i-i*3+3)%mod;
			ll x=(i*i*i-i*i*3+i*2)%mod;
			ll y=(i*i-i)%mod;
			ll mm=m-1;
			ll b00=1,b01=0,b10=0,b11=1;
			while(mm){
				if(mm&1){
					ll bb00=(b00*a00+b01*a10)%mod;
					ll bb01=(b00*a01+b01*a11)%mod;
					ll bb10=(b10*a00+b11*a10)%mod;
					ll bb11=(b10*a01+b11*a11)%mod;
					b00=bb00;
					b01=bb01;
					b10=bb10;
					b11=bb11;
				}
				ll aa00=(a00*a00+a01*a10)%mod;
				ll aa01=(a00*a01+a01*a11)%mod;
				ll aa10=(a10*a00+a11*a10)%mod;
				ll 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*=comb(k,i))%=mod;
		if((k-i)%2==1)
			tmp=(-tmp+mod)%mod;
		(ans+=tmp)%=mod;
	}
	cout<<ans<<endl;
}
0