結果

問題 No.391 CODING WAR
コンテスト
ユーザー hondo
提出日時 2020-05-09 17:21:40
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 33 ms / 2,000 ms
コード長 3,192 bytes
コンパイル時間 2,565 ms
コンパイル使用メモリ 78,776 KB
実行使用メモリ 8,320 KB
最終ジャッジ日時 2024-07-05 22:21:15
合計ジャッジ時間 2,067 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
 * yuki/391/main.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> ostream & operator << (ostream & out, vector<T> const & v) {
  for (auto &&a: v) out << a << " "; out << endl; return out;
}
template <class T> void dump(T &a) { cout << a << endl; }
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

/* Mod */
#define MOD 1000000007
struct mint {
  ll x;
  mint():x(0){}
  mint(ll x):x((x%MOD+MOD)%MOD){}
  // mint(ll x):x(x){}
  mint& fix() { x = (x%MOD+MOD)%MOD; return *this;}
  mint operator-() const { return mint(0) - *this;}
  mint& operator+=(const mint& a){ if((x+=a.x)>=MOD) x-=MOD; return *this;}
  mint& operator-=(const mint& a){ if((x+=MOD-a.x)>=MOD) x-=MOD; return *this;}
  mint& operator*=(const mint& a){ (x*=a.x)%=MOD; return *this;}
  mint operator+(const mint& a)const{ return mint(*this) += a;}
  mint operator-(const mint& a)const{ return mint(*this) -= a;}
  mint operator*(const mint& a)const{ return mint(*this) *= a;}
  bool operator<(const mint& a)const{ return x < a.x;}
  bool operator==(const mint& a)const{ return x == a.x;}
};
ostream & operator << (ostream & out, mint const & v) {
  out << v.x;
  return out;
}
template<class T1, class T2>
T1 intpow(const T1& a, const T2 n) {
  if (n == 0) return 1;
  auto t = intpow(a, n / 2);
  t = t * t;
  if (n & 1) t = t * a;
  return t;
}

/* nCk */
template<class T> struct BiCoef {
    vector<T> fact_, inv_, finv_;
    constexpr BiCoef() {}
    constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) {
        init(n);
    }
    constexpr void init(int n) noexcept {
        fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);
        for(int i = 2; i < n; i++){
            fact_[i] = fact_[i-1] * i;
            inv_[i] = -inv_[MOD%i] * (MOD/i);
            finv_[i] = finv_[i-1] * inv_[i];
        }
    }
    constexpr T com(int n, int k) const noexcept {
        if (n < k || n < 0 || k < 0) return 0;
        return fact_[n] * finv_[k] * finv_[n-k];
    }
    constexpr T fact(int n) const noexcept {
        if (n < 0) return 0;
        return fact_[n];
    }
    constexpr T inv(int n) const noexcept {
        if (n < 0) return 0;
        return inv_[n];
    }
    constexpr T finv(int n) const noexcept {
        if (n < 0) return 0;
        return finv_[n];
    }
};
/*
 * 区別ある人(玉)を区別ある問題(箱)に1人ずつ以上ずつ当てはめる問題.
 * sum((-1)^(k-1)*kCi*i^n | for i in [0, k])
 */
ll N, M;
BiCoef<mint> bc;
void solve() {
  cin >> N >> M;
  if (N < M) {
    cout << 0 << endl;
    return;
  }
  bc.init(210000);
  mint sum = 0;
  for (ll i=0; i<=M; i++) {
    mint sign = 1;
    if ((M-i)%2 == 1) sign *= -1;
    sum += sign * bc.com(M, i) * intpow(mint(i), N);
  }
  cout << sum << endl;
}
int main() {
  // cout.precision(15); cout << fixed;

  solve();

  return 0;
}
0