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

• 問題: No.391 CODING WAR
• ユーザー: morimario
• 提出日時: 2022-10-26 16:04:27
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 129 ms / 2,000 ms
• コード長: 6,205 bytes
• コンパイル時間: 3,777 ms
• コンパイル使用メモリ: 253,900 KB
• 最終ジャッジ日時: 2025-02-08 12:47:39
• ジャッジサーバーID （参考情報）: judge1 / judge5

ファイルパターン	結果
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
// 2022.10.21
// #define _GLIBCXX_DEBUG //
// #define __USE_MATH_DEFINES // const double PI = acos(-1.0)
#include <bits/stdc++.h>
using namespace std;
// (*) snipet
// type name
using ll = long long;
using pii = pair<int, int>; using pil = pair<int, ll>; using pli = pair<ll, int>; using pll = pair<ll, ll>;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>;
using vpii = vector<pii>; using vpil = vector<pil>; using vpli = vector<pli>; using vpll = vector<pll>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>;
template <typename T> using pq = priority_queue<T, vector<T>>;
template <typename T> using pql = priority_queue<T, vector<T>, greater<T>>;
// rep
#define rep0(goal) for (int cnt = 0; cnt < int(goal); ++cnt)
#define rep(cnt, goal) for (int cnt = 0; cnt < int(goal); ++cnt)
#define rep2(cnt, start, goal) for (int cnt = int(start); cnt < int(goal); ++cnt)
#define rep3(cnt, start, goal) for (int cnt = int(start); cnt > int(goal); --cnt)
// all
#define all(ctn) begin(ctn), end(ctn)
// chmax, chmin
template <typename T> bool chmax(T &x, const T y) { if (x < y) { x = y; return true; } else { return false; }}
template <typename T> bool chmin(T &x, const T y) { if (x > y) { x = y; return true; } else { return false; }}
// etc.
void Yn(const bool &exp) { if (exp) cout << "Yes" << endl; else cout << "No" << endl;}
void set_prec(const int &dig) { cout << fixed << setprecision(dig); cerr << fixed << setprecision(dig);}
// template <typename T> T INF() { return numeric_limits<T>::max();}
// template <typename T> T MIN_INF() { return numeric_limits<T>::min();}
#include <atcoder/all>
using namespace atcoder;
// using mint = atcoder::modint1000000007;
using mint = atcoder::modint998244353;
// using mint = atcoder::modint;
void pr(const mint &MINT) { cerr << MINT.val(); } // mint
using pmm = pair<mint, mint>; using pim = pair<int, mint>; using pmi = pair<mint, int>; using plm = pair<ll, mint>; using pml = pair<mint, ll>;
using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>;
// debug
template <typename T> void pr(const T &obj) { cerr << obj; } // single
template <typename T, typename ...Ts> void pr(const T &first, const Ts &...rest) { pr(first); cerr << ", "; pr(rest...); } // multi(plural)
template <typename S, typename T> void pr(const pair<S, T> &PAIR) { cerr << "("; pr(PAIR.first); cerr << ", "; pr(PAIR.second); cerr << ")"; } // 
    pair
template <typename S, typename T, typename U> void pr(const tuple<S, T, U> &trp) { cerr << "("; pr(get<0>(trp)); cerr << ", "; pr(get<1>(trp)); cerr 
    << ", "; pr(get<2>(trp)); cerr << ")"; } // tuple(3)
template <typename T> void pr(const vector<T> &vec) { cerr << "{"; for (T obj : vec) { pr(obj); cerr << ", "; } cerr << "}"; } // vector
template <typename T> void pr(const vector<vector<T>> &vv) { rep(row, vv.size()) { cerr << endl; cerr << "[" << row << "]: "; pr(vv[row]); }} // 
    vector(multi-D)
template <typename T> void pr(const set<T> &SET) { cerr << "{"; for (T obj : SET) { pr(obj); cerr << ", "; } cerr << "}"; } // set
template <typename T> void pr(const multiset<T> &MS) { cerr << "{"; for (T obj : MS) { pr(obj); cerr << ", "; } cerr << "}"; } // multiset
template <typename S, typename T> void pr(const map<S, T> &MAP) { cerr << "{"; for (pair<S, T> p : MAP) { pr(p.first); cerr << ": "; pr(p.second); 
    cerr << ", "; } cerr << "}";} // map
template <typename T> void pr(const queue<T> &que) { queue<T> q = que; cerr << "{"; while (!q.empty()) { pr(q.front()); q.pop(); cerr << ", ";} cerr 
    << "}";} // queue
template <typename T> void pr(const deque<T> &deq) { deque<T> d = deq; cerr << "{"; while (!d.empty()) { pr(d.front()); d.pop_front(); cerr << ", ";} 
    cerr << "}";} // deque
template <typename T> void pr(const stack<T> &stc) { stack<T> s = stc; vector<T> v; while (!s.empty()) { v.push_back(s.top()); s.pop();} reverse(all
    (v)); cerr << "{"; for (T obj : v) cerr << obj << ", "; cerr << "}";} // stack
template <typename T> void pr(const priority_queue<T> &pq) { priority_queue<T> p = pq; cerr << "{"; while (!p.empty()) { pr(p.top()); p.pop(); cerr 
    << ", "; } cerr << "}";} // priority_queue
template <typename T> void pr(const priority_queue<T, vector<T>, greater<T>> &pq) { priority_queue<T, vector<T>, greater<T>> p = pq; cerr << "{"; 
    while (!p.empty()) { pr(p.top()); p.pop(); cerr << ", ";} cerr << "}";} // priority_queue(from less)
#define db(obj) cerr << #obj << ": "; pr(obj); cerr << " ";
#define dl(obj) db(obj); cerr << endl;
#define dm(...) cerr << "(" << #__VA_ARGS__ << "): ("; pr(__VA_ARGS__); cerr << ") ";
#define dml(...) dm(__VA_ARGS__); cerr << endl;
// N元集合からM元集合への全射の数
// N -> n, M -> k
// global
ll N;
int M;
vl fac; // fac[i] = i!
vl inv; // inv[i] = 1/i! mod m
ll m = 1e9 + 7; // 998244353; // MOD
void input() {
    cin >> N >> M;
}
ll my_pow_mod(ll x, ll n, ll m) {
    assert(0 <= n); assert(1 <= m);
    ll res = 1;
    ll y = x % m;
    if (x < 0) x += m;
    while (n) {
        if (n % 2) {
            res = (res * y) % m;
        }
        n /= 2;
        y = (y * y) % m;
    }
    return res;
}
ll my_inv_mod(ll x, ll m) {
    assert(1 <= m);
    assert(x % m != 0); // m: 素数
    return my_pow_mod(x, m - 2, m);
    // assert(my_gcd(x, m) == 1);
    // return my_pow_mod(x, phi(m) - 1, m);
}
// factorial, inv_factorial
vl my_facts(int N) {
    assert(0 <= N);
    vl res(N + 1);
    res[0] = 1;
    rep(i, N) res[i + 1] = (res[i] * (i + 1)) % m;
    return res;
}
vl my_inv_facts(int N) {
    assert(0 <= N);
    vl res(N + 1);
    res[0] = 1;
    rep(i, N) res[i + 1] = (res[i] * my_inv_mod(i + 1, m)) % m;
    return res;
}
void init() {
    fac = my_facts(M + 1);
    inv = my_inv_facts(M + 1);
}
ll surjection(ll n, int k) { // O(k*logn)
    assert(0 <= n); assert(0 <= k);
    // if (n < k) return 0;
    ll res = 0;
    rep(i, k + 1) {
        ll temp = ((fac[k] * inv[k - i] % m) * inv[i] % m);
        temp = (temp * my_pow_mod(i, n, m)) % m;
        if ((k - i) % 2 == 0) res = (res + temp) % m;
        else res = (res - temp + m) % m;
    }
    return res;
}
void solve() {
    cout << surjection(N, M) << endl;
};
int main() {
    input();
    init();
    solve();
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX