結果

問題 No.8053 2.5 色で色塗り
コンテスト
ユーザー id-ord
提出日時 2026-01-05 19:10:23
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 374 ms / 2,000 ms
コード長 697 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,316 ms
コンパイル使用メモリ 148,120 KB
実行使用メモリ 198,988 KB
最終ジャッジ日時 2026-01-05 19:10:28
合計ジャッジ時間 3,685 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
constexpr int64_t p=1'000'000'007;
constexpr int64_t k=(p+5)/2;
int64_t invtbl[5001],T[5001][5001];
int main(){
	invtbl[1]=1;T[1][1]=1;
	for (int i = 2; i < 5001; i++) {
		invtbl[i]=p-(invtbl[p%i]*(p/i))%p;
		T[i][1]=1;
		T[0][i]=0;
	}
	for (int n = 2; n < 5001; n++) {
		for (int k = 1; k < 5001; k++) {
			T[n][k]=(T[n-1][k-1]+T[n-1][k])*k;
			T[n][k]%=p;
		}
	}
	int64_t N,M,kCi=1,kCj,ans=0;
	std::cin>>N>>M;
	for(int64_t i=1;i<=N;i++){
		kCj=1;
		kCi=(((kCi*(k+1-i))%p)*(invtbl[i]))%p;
		int64_t l=T[N][i];
		for(int64_t j=1;j<=M;j++){
			kCj=(((kCj*(k+1-i-j))%p)*(invtbl[j]))%p;
			int64_t r=T[M][j];
			ans+=(((kCi*l)%p)*((kCj*r)%p));
			ans%=p;
		}
	}
	std::cout<<ans;
}
0