#864476 (C++17) No.391 CODING WAR

• 問題: No.391 CODING WAR
• ユーザー: batasanblog
• 提出日時: 2023-04-29 15:19:15
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 21 ms / 2,000 ms
• コード長: 2,352 bytes
• コンパイル時間: 3,539 ms
• コンパイル使用メモリ: 255,568 KB
• 最終ジャッジ日時: 2025-02-12 15:59:15
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
sample	AC * 4
other	AC * 16

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
//using mint = static_modint<998244353>;
//using mint = modint;
using mint = static_modint<1000000007>;
using vm = vector<mint>;
using vvm = vector<vm>;
ostream &operator<<(ostream &o,const mint &m){cout<<m.val();return o;}
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using pl = pair<ll,ll>;
using vp = vector<pl>;
#define rep(i,n) for(ll i=0;i<(ll)(n);++i)
#define reps(i,s,n) for(ll i=(s);i<(ll)(n);++i)
#define rep1(i,n) for(ll i=1;i<=(ll)(n);++i)
template<typename T>inline bool chmax(T &a,T b){return a<b?a=b,true:false;}
template<typename T>inline bool chmin(T &a,T b){return a>b?a=b,true:false;}
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define be(v) (v).begin(),(v).end()
const long long INF = 1e18;
#ifdef DEBUG
#include <debug.hpp>
#endif
// combination mod prime
// https://youtu.be/8uowVvQ_-Mo?t=6002
// https://youtu.be/Tgd_zLfRZOQ?t=9928
struct modinv {
  int n; vector<mint> d;
  modinv(): n(2), d({0,1}) {}
  mint operator()(int i) {
    while (n <= i) d.push_back(-d[mint::mod()%n]*(mint::mod()/n)), ++n;
    return d[i];
  }
  mint operator[](int i) const { return d[i];}
} invs;
struct modfact {
  int n; vector<mint> d;
  modfact(): n(2), d({1,1}) {}
  mint operator()(int i) {
    while (n <= i) d.push_back(d.back()*n), ++n;
    return d[i];
  }
  mint operator[](int i) const { return d[i];}
} facts;
struct modfactinv {
  int n; vector<mint> d;
  modfactinv(): n(2), d({1,1}) {}
  mint operator()(int i) {
    while (n <= i) d.push_back(d.back()*invs(n)), ++n;
    return d[i];
  }
  mint operator[](int i) const { return d[i];}
} ifacts;
mint comb(int n, int k) {
  if (n < k || k < 0) return 0;
  return facts(n)*ifacts(k)*ifacts(n-k);
}
int main(){
#ifdef DEBUG
    cout << "--- Input ---" << endl;
#endif
    ll N,M;cin>>N>>M;
#ifdef DEBUG
    cout<<N<<" "<<M<<endl;
    cout << "--- Logic ---" << endl;
#endif
    mint ans=0;
    rep(m,M+1){
        mint c=comb(M,m);
#ifdef DEBUG
        cout<<"M="<<M<<" m="<<m<<" c="<<c<<" pow="<<mint(m).pow(N)<<endl;
#endif
        c*=mint(m).pow(N);
        if((M-m)&1)ans-=c;
        else ans+=c;
#ifdef DEBUG
        cout<<" ans="<<ans<<endl;
#endif
    }
#ifdef DEBUG
    cout << "--- Answer ---" << endl;
#endif
    cout<<ans<<endl;
    return 0;
}
//cout << fixed << setprecision(9);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX