結果

問題 No.391 CODING WAR
ユーザー grun1301grun1301
提出日時 2021-06-26 14:56:36
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 74 ms / 2,000 ms
コード長 3,316 bytes
コンパイル時間 981 ms
コンパイル使用メモリ 82,932 KB
実行使用メモリ 22,368 KB
最終ジャッジ日時 2023-09-07 15:18:48
合計ジャッジ時間 2,748 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 21 ms
22,104 KB
testcase_01 AC 21 ms
22,144 KB
testcase_02 AC 21 ms
22,172 KB
testcase_03 AC 21 ms
22,368 KB
testcase_04 AC 21 ms
22,300 KB
testcase_05 AC 22 ms
22,156 KB
testcase_06 AC 21 ms
22,100 KB
testcase_07 AC 21 ms
22,100 KB
testcase_08 AC 21 ms
22,164 KB
testcase_09 AC 74 ms
22,116 KB
testcase_10 AC 68 ms
22,092 KB
testcase_11 AC 40 ms
22,200 KB
testcase_12 AC 21 ms
22,104 KB
testcase_13 AC 61 ms
22,304 KB
testcase_14 AC 57 ms
22,148 KB
testcase_15 AC 62 ms
22,088 KB
testcase_16 AC 45 ms
22,100 KB
testcase_17 AC 51 ms
22,140 KB
testcase_18 AC 42 ms
22,160 KB
testcase_19 AC 41 ms
22,100 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>
#include <queue>
#include <string>
#include <string.h>
#include <istream>
#include <ostream>

#define reps(i,s,n) for(int (i) = (s); (i) < (n); (i)++)
#define rep(i,n) reps(i,0,n)
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int> ;
using vl = vector<ll>;

//https://yukicoder.me/problems/918

//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 600000 //10^5:配列の最大のrange(素数列挙などで使用)

template<ll mod> class modint{
    public:
    ll val=0;
    //コンストラクタ
    modint(ll x=0){while(x<0)x+=mod;val=x%mod;}
    //コピーコンストラクタ
    modint(const modint &r){val=r.val;}
    //算術演算子
    modint operator -(){return modint(-val);} //単項
    modint operator +(const modint &r){return modint(*this)+=r;}
    modint operator -(const modint &r){return modint(*this)-=r;}
    modint operator *(const modint &r){return modint(*this)*=r;}
    modint operator /(const modint &r){return modint(*this)/=r;}
    //代入演算子
    modint &operator +=(const modint &r){
        val+=r.val;
        if(val>=mod)val-=mod;
        return *this;
    }
    modint &operator -=(const modint &r){
        if(val<r.val)val+=mod;
        val-=r.val;
        return *this;
    }
    modint &operator *=(const modint &r){
        val=val*r.val%mod;
        return *this;
    }
    modint &operator /=(const modint &r){
        ll a=r.val,b=mod,u=1,v=0;
        while(b){
            ll t=a/b;
            a-=t*b;swap(a,b);
            u-=t*v;swap(u,v);
        }
        val=val*u%mod;
        if(val<0)val+=mod;
        return *this;
    }
    //等価比較演算子
    bool operator ==(const modint& r){return this->val==r.val;}
    bool operator <(const modint& r){return this->val<r.val;}
    bool operator !=(const modint& r){return this->val!=r.val;}
};

using mint = modint<MOD>;

//入出力ストリーム
istream &operator >>(istream &is,mint& x){//xにconst付けない
    ll t;is >> t;
    x=t;
    return (is);
}
ostream &operator <<(ostream &os,const mint& x){
    return os<<x.val;
}

//累乗
mint modpow(const mint &a,ll n){
    if(n==0)return 1;
    mint t=modpow(a,n/2);
    t=t*t;
    if(n&1)t=t*a;
    return t;
}

//二項係数の計算
mint fac[MAXR+1],finv[MAXR+1],inv[MAXR+1],perm[MAXR+1];
//テーブルの作成
void COMinit() {
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    reps(i,2,MAXR+1){
        fac[i]=fac[i-1]*mint(i);
        inv[i]=-inv[MOD%i]*mint(MOD/i);
        finv[i]=finv[i-1]*inv[i];
    }
    perm[0]=1;
    
    rep(i,MAXR){
        perm[i+1]=mint(i+1)*perm[i];
    }
}
//演算部分
mint COM(ll n,ll k){
    if(n<k)return 0;
    if(n<0 || k<0)return 0;
    return fac[n]*finv[k]*finv[n-k];
}

mint PERM(ll n,ll k){
    return COM(n,k)*perm[k];
}

int main(){
    COMinit();
    ll n,m;
    cin >> n >> m;
    mint ans = 0;
    rep(i,m){
        mint tmp = 1;
        
        tmp = COM(m,i);
        tmp = tmp * modpow(m-i,n);
        if(i % 2 == 0){
            ans += tmp;
        }else{
            ans -= tmp;
        }
    }

    cout << ans << endl;
    return 0;
}
0