結果
問題 | No.2351 Butterfly in Summer |
ユーザー |
![]() |
提出日時 | 2023-06-16 21:48:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 15 ms / 2,000 ms |
コード長 | 1,153 bytes |
コンパイル時間 | 957 ms |
コンパイル使用メモリ | 107,924 KB |
最終ジャッジ日時 | 2025-02-14 05:09:17 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <algorithm> #include <bit> #include <cassert> #include <cstdio> #include <cstdlib> #include <cmath> #include <deque> #include <iostream> #include <map> #include <unordered_set> #include <unordered_map> #include <vector> #include <set> #include <string> using namespace::std; struct GcdResult { long long g; long long x; long long y; }; GcdResult gcd(long long a, long long b) { assert(a > 0); assert(b > 0); //cerr << "gcd " << a << ", " << b << endl; if (b > a) { GcdResult r = gcd(b, a); swap(r.x, r.y); return r; } if (a % b) { GcdResult r = gcd(a % b, b); r.y -= r.x * (a / b); return r; } else { return {b, 0, 1}; } } long long inv(long long a, long long m=998244353) { GcdResult r = gcd(a, m); assert(r.g == 1); long long result = (r.x % m + m) % m; assert(0 <= result); assert(result < m); return result; } int main() { ios::sync_with_stdio(false); long long n, k, m = 998244353; cin >> n >> k; long long r = ((k - 1) * n) % m; long long inv_k = inv(k); for (int i = 0; i < n - 1; ++i) r = (r * inv_k) % m; cout << r << endl; return 0; }