結果
問題 | No.391 CODING WAR |
ユーザー | grun1301 |
提出日時 | 2021-06-26 14:56:36 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 60 ms / 2,000 ms |
コード長 | 3,316 bytes |
コンパイル時間 | 810 ms |
コンパイル使用メモリ | 84,624 KB |
実行使用メモリ | 22,400 KB |
最終ジャッジ日時 | 2024-06-25 09:08:12 |
合計ジャッジ時間 | 2,334 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 21 ms
22,400 KB |
testcase_01 | AC | 20 ms
22,400 KB |
testcase_02 | AC | 20 ms
22,272 KB |
testcase_03 | AC | 22 ms
22,268 KB |
testcase_04 | AC | 21 ms
22,144 KB |
testcase_05 | AC | 22 ms
22,144 KB |
testcase_06 | AC | 22 ms
22,268 KB |
testcase_07 | AC | 22 ms
22,144 KB |
testcase_08 | AC | 22 ms
22,400 KB |
testcase_09 | AC | 60 ms
22,144 KB |
testcase_10 | AC | 52 ms
22,268 KB |
testcase_11 | AC | 41 ms
22,272 KB |
testcase_12 | AC | 20 ms
22,144 KB |
testcase_13 | AC | 52 ms
22,272 KB |
testcase_14 | AC | 50 ms
22,272 KB |
testcase_15 | AC | 55 ms
22,268 KB |
testcase_16 | AC | 42 ms
22,276 KB |
testcase_17 | AC | 46 ms
22,272 KB |
testcase_18 | AC | 38 ms
22,272 KB |
testcase_19 | AC | 37 ms
22,148 KB |
ソースコード
#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; }