結果

問題 No.391 CODING WAR
ユーザー btk
提出日時 2016-07-08 23:18:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 68 ms / 2,000 ms
コード長 1,278 bytes
コンパイル時間 1,507 ms
コンパイル使用メモリ 167,628 KB
実行使用メモリ 15,232 KB
最終ジャッジ日時 2024-10-13 06:50:21
合計ジャッジ時間 2,877 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;

struct INIT{INIT(){ios::sync_with_stdio(false);cin.tie(0);cout<<fixed;cout<<setprecision(10);}}init;
#define rep(i,n) for(auto i=(n)*0;i<n;i++)
#define range(it,v) for(auto &it:v)


typedef long long LL;
const int MOD=(int)(1e9+7);

LL fact[2000000];
struct init2{
    init2(){
	fact[0]=1;
	rep(i,1500000)fact[i+1]=fact[i]*(i+1)%MOD;
    }
}i2;
// a x + b y = gcd(a, b)
// O(log (a+b) )
LL extgcd(LL a, LL b, LL &x, LL &y) {
  LL g = a; x = 1; y = 0;
  if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
  return g;
}

// mを法とするaの逆元
// O(log a)
LL invMod(LL a) {
	LL x, y;
	if (extgcd(a, MOD, x, y) == 1)return (x + MOD) % MOD;
	else	 return 0; // unsolvable
}


LL Comb(LL n,LL k){
	LL u=fact[n];
	LL d=(fact[k]*fact[n-k])%MOD;
	return (u*invMod(d))%MOD;
}


//a^n (mod MOD)
//O(log a)
LL pow_mod(LL a,LL n){
    a%=MOD;
    LL res=1;
    LL b=1;
    while(n>=b){
	if(n&b)
	    res=(res*a)%MOD;
	a=(a*a)%MOD;
	b<<=1;
	}
    return res;
}


int main(){
    LL N,M;
    cin>>N>>M;
    if(N<M)cout<<0<<endl;
    else {
	LL res=0;
	for(int i=0;i<M;i++)
	    if(i&1)res=(res+MOD-Comb(M,M-i)*pow_mod(M-i,N)%MOD)%MOD;
	    else res=(res+Comb(M,M-i)*pow_mod(M-i,N)%MOD)%MOD;
	cout<<res<<endl;
    }
    return 0;
}
0