結果

問題 No.391 CODING WAR
コンテスト
ユーザー t_mk
提出日時 2022-03-19 16:11:11
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 182 ms / 2,000 ms
コード長 1,465 bytes
コンパイル時間 1,396 ms
コンパイル使用メモリ 167,192 KB
実行使用メモリ 6,656 KB
最終ジャッジ日時 2024-10-04 18:16:02
合計ジャッジ時間 5,216 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i < (n);i++)
using ll = long long;
using P =pair<int,int>;
ll INF = 1LL << 60;
long long modpow(long long a, long long b, long long m) {
	// a^b mod m を求める
	long long p = 1, q = a;
	for (int i = 0; i < 30; i++) {
		if ((b & (1LL << i)) != 0) {
			p *= q; p %= m;
		}
		q *= q; q %= m;
	}
	return p;
}

long long Div(long long a, long long b, long long m) {
	// a÷b の mod m での逆元を求める
	return (a * modpow(b, m - 2, m)) % m;
}

// 変数
long long mod = 1000000007;
long long N;
long long fact[200009]; // 階乗
long long factinv[200009];//　階乗の逆元
//階乗を求める
void init() {
	fact[0] = 1;
	for (int i = 1; i <= 200000; i++) fact[i] = (1LL * i * fact[i - 1]) % mod;
	for (int i = 0; i <= 200000; i++) factinv[i] = Div(1, fact[i], mod);
}

long long ncr(int n, int r) {
	if (n < r || r < 0) return 0;
	return (fact[n] * factinv[r] % mod) * factinv[n - r] % mod;
}

ll pown(ll n,ll k){
  ll ans = 1;
  while(k > 0){
    if(k & 1)ans *= n;
    n *= n;
    k /= 2;
    n %= mod;
    ans %= mod;
  }
  return ans;
}
int main(){
  ll n,m;
  cin >> n >> m;
  ll ans = 0;
  init();
  for(int i = m;i >= 1;i--){
    if((i-m)%2 == 0){
      ll k = pown(i,n)*ncr(m,i);
      k %= mod;
      ans += k;
    }else {
      ll k = pown(i,n)*ncr(m,i);
      k %= mod;
      ans -= k;
    }
    ans += mod;
    ans %= mod;
  }
  cout << ans << endl;
  return 0;
}
0