結果

問題 No.391 CODING WAR
コンテスト
ユーザー Kutimoti_T
提出日時 2018-09-03 23:11:54
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 22 ms / 2,000 ms
コード長 5,394 bytes
コンパイル時間 1,451 ms
コンパイル使用メモリ 162,184 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-09 19:45:18
合計ジャッジ時間 2,225 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

long long inv_mod(long long a, long long m) {
  long long b, x, u, q, abs_m, tmp;

  abs_m = (m < 0) ? -m : m;
  b = m;
  x = 1;
  u = 0;
  while (b > 0) {
    q = a / b;
    tmp = u;
    u = x - q * u;
    x = tmp;
    tmp = b;
    b = a - q * b;
    a = tmp;
  }

  return (x < 0) ? abs_m + x : x;
}
template <long long MOD>
struct ModInt{
  long long value;

  ModInt(long long n = 0) {
    if(n >= 0) value = n % MOD;
    else value = (MOD + (n % MOD));
  }

  operator long long() const noexcept {return value % MOD;}

  ModInt<MOD> operator++(int){
    ModInt<MOD> before = *this;
    value = (value + 1) % MOD;
    return before;
  }

  ModInt<MOD> operator--(int){
    ModInt<MOD> before = *this;
    value = (value - 1 + MOD) % MOD;
    return before;
  }

  ModInt<MOD>& operator++(){
    value = (value + 1) % MOD;
    return *this;
  }

  ModInt<MOD>& operator--(){
    value = (value - 1 + MOD) % MOD;
    return *this;
  }

  bool operator!() const noexcept{
    return !static_cast<bool>(value);
  }

  ModInt<MOD> operator+() const{
    return value;
  }
  
  ModInt<MOD> operator-() const{
    return (-value + MOD) % MOD;
  }

  ModInt<MOD>& operator*=(const ModInt<MOD>& m){
    return *this = ModInt<MOD>((this->value * m.value) % MOD);
  }
  ModInt<MOD>& operator+=(const ModInt<MOD>& m){
    return *this = ModInt<MOD>((this->value + m.value) % MOD);
  }
  ModInt<MOD>& operator-=(const ModInt<MOD>& m){
    return *this = ModInt<MOD>((this->value - m.value + MOD) % MOD);
  }
  ModInt<MOD>& operator/=(const ModInt<MOD>& m){
    return *this = ModInt<MOD>((this->value * inv_mod(m.value,MOD)) % MOD);
  }
 };

template<long long MOD>
ModInt<MOD> operator*(const ModInt<MOD>& m1,const ModInt<MOD>& m2){return ModInt<MOD>(m1) *= m2;}
template<long long MOD>
ModInt<MOD> operator+(const ModInt<MOD>& m1,const ModInt<MOD>& m2){return ModInt<MOD>(m1) += m2;}
template<long long MOD>
ModInt<MOD> operator-(const ModInt<MOD>& m1,const ModInt<MOD>& m2){return ModInt<MOD>(m1) -= m2;}
template<long long MOD>
ModInt<MOD> operator/(const ModInt<MOD>& m1,const ModInt<MOD>& m2){return ModInt<MOD>(m1) /= m2;}
template<long long MOD>
ModInt<MOD> operator*(const long long& m1,const ModInt<MOD>& m2){return ModInt<MOD>(m1) *= m2;}
template<long long MOD>
ModInt<MOD> operator+(const long long& m1,const ModInt<MOD>& m2){return ModInt<MOD>(m1) += m2;}
template<long long MOD>
ModInt<MOD> operator-(const long long& m1,const ModInt<MOD>& m2){return ModInt<MOD>(m1) -= m2;}
template<long long MOD>
ModInt<MOD> operator/(const long long& m1,const ModInt<MOD>& m2){return ModInt<MOD>(m1) /= m2;}


template<long long MOD>
struct Fact_Node{
  ModInt<MOD> fact;
  ModInt<MOD> inv_fact;

  ModInt<MOD> operator+() const{
    return fact;
  }
  
  ModInt<MOD> operator-() const{
    return -fact;
  }

  Fact_Node<MOD>& operator*=(const ModInt<MOD>& m){
    fact *= m;
    inv_fact *= m;
    return *this;
  }
  Fact_Node<MOD>& operator/=(const ModInt<MOD>& m){
    fact /= m;
    inv_fact /= m;
    return *this;
  }

  Fact_Node<MOD>& operator*=(const Fact_Node<MOD>& f){
    fact *= f.fact;
    inv_fact *= f.inv_fact;
    return *this;
  }
  Fact_Node<MOD>& operator/=(const Fact_Node<MOD>& f){
    fact *= f.inv_fact;
    inv_fact *= f.fact;
    return *this;
  }
};
template<long long MOD>
Fact_Node<MOD> operator*(const Fact_Node<MOD>& m1,const ModInt<MOD>& m2){return Fact_Node<MOD>(m1) *= m2;}
template<long long MOD>
Fact_Node<MOD> operator/(const Fact_Node<MOD>& m1,const ModInt<MOD>& m2){return Fact_Node<MOD>(m1) /= m2;}
template<long long MOD>
Fact_Node<MOD> operator*(const ModInt<MOD>& m1,const Fact_Node<MOD>& m2){return Fact_Node<MOD>(m2) *= m1;}
template<long long MOD>
Fact_Node<MOD> operator/(const ModInt<MOD>& m1,const Fact_Node<MOD>& m2){return {m1 * m2.inv_fact , m2.fact / m1};}
template<long long MOD>
Fact_Node<MOD> operator*(const Fact_Node<MOD>& m1,const Fact_Node<MOD>& m2){return Fact_Node<MOD>(m1) *= m2;}
template<long long MOD>
Fact_Node<MOD> operator/(const Fact_Node<MOD>& m1,const Fact_Node<MOD>& m2){return Fact_Node<MOD>(m1) /= m2;}

#include <vector>
#include <iostream>
using namespace std;

template<long long MOD>
struct Facts{
  vector<ModInt<MOD>> facts;
  vector<ModInt<MOD>> inv_facts;
  using Node = Fact_Node<MOD>;
  Facts(int N) : facts(N,1) , inv_facts(N){
    for(int i = 1;i < N;i++){
      facts[i] = facts[i - 1] * i;
    }
    inv_facts[N - 1] = 1LL /  facts[N - 1];

    for(int i = N - 1;i >= 1;i--){
      inv_facts[i - 1] = inv_facts[i] * i;
    }
  }

  Node operator[](int n){
    return (Fact_Node<MOD>){facts[n],inv_facts[n]};
  }

  Node nCr(int n,int r){
    return (*this)[n] / (*this)[r] / (*this)[n - r];
  }

  Node nHr(int n,int r){
    return this->nCr(n + r - 1,r);
  }
};
template<long long MOD>
ModInt<MOD> mod_pow(ModInt<MOD> a, i64 b){
  ModInt<MOD> ans = 1;
  while(b){
    if(b & 1) ans *= a;
    a *= a;
    b >>= 1;
  }
  return ans;
}
int main(){
  i64 N,M;
  cin >> N >> M;
  const i64 MMM = 1e9 + 7;
  Facts<MMM> fact(M + 100);
  using Int = ModInt<MMM>;
  Int ans = mod_pow(Int(M),N);
  for(int i = 1;i <= M;i++){
    i64 re = (fact.nCr(M,i).fact * mod_pow(Int(M - i) , N));
    if(i & 1) ans -= re;
    else ans += re;
  }
  cout << ans << endl;
}
0