結果

問題 No.1035 Color Box
コンテスト
ユーザー autumn-eel
提出日時 2020-04-24 21:35:25
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 13 ms / 2,000 ms
コード長 1,109 bytes
コンパイル時間 1,567 ms
コンパイル使用メモリ 172,872 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2024-10-15 02:28:00
合計ジャッジ時間 2,529 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int>P;
typedef long long ll;

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

ll ppow(ll a,ll b){
	a%=MOD;
	ll res=1;
	while(b){
		if(b&1)res=(res*a)%MOD;
		a=(a*a)%MOD;
		b>>=1;
	}
	return res;
}
class Fact{
	vector<ll>fact;
	vector<ll>inv;
public:
	Fact(){}
	Fact(int n){
		n=n*2+10;
		fact=inv=vector<ll>(n);
		fact[0]=inv[0]=1;
		for(int i=1;i<n;i++){
			fact[i]=(fact[i-1]*i)%MOD;
		}
		inv[n-1]=ppow(fact[n-1],MOD-2);
		for(int i=n-2;i>=0;i--){
			inv[i]=(inv[i+1]*(i+1))%MOD;
		}
	}
	ll get(int n){
		return fact[n];
	}
	ll get_inv(int n){
		return inv[n];
	}
	ll nPr(int n,int r){
		return fact[n]*inv[n-r]%MOD;
	}
	ll nCr(int n,int r){
		return nPr(n,r)*inv[r]%MOD;
	}
	ll nrP(int n,int r){
		return nPr(n+r,n);
	}
	ll nrC(int n,int r){
		return nCr(n+r,n);
	}
};
int main(){
	int n,m;cin>>n>>m;
	Fact fac(m);
	ll ans=ppow(m,n);
	for(int i=1;i<m;i++){
		ll d=ppow(m-i,n)*fac.nCr(m,i)%MOD;
		if(i&1)(ans+=MOD-d)%=MOD;
		else (ans+=d)%=MOD;
	}
	cout<<ans<<endl;
}
0