結果
問題 | No.2351 Butterfly in Summer |
ユーザー | GEX777 |
提出日時 | 2023-06-16 21:32:47 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 12,534 bytes |
コンパイル時間 | 3,675 ms |
コンパイル使用メモリ | 204,120 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-24 13:09:13 |
合計ジャッジ時間 | 4,479 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | WA | - |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | AC | 2 ms
6,940 KB |
testcase_12 | AC | 2 ms
6,944 KB |
testcase_13 | WA | - |
testcase_14 | AC | 2 ms
6,944 KB |
testcase_15 | WA | - |
testcase_16 | AC | 1 ms
6,940 KB |
testcase_17 | AC | 1 ms
6,940 KB |
testcase_18 | AC | 1 ms
6,940 KB |
testcase_19 | AC | 2 ms
6,940 KB |
testcase_20 | WA | - |
testcase_21 | AC | 2 ms
6,940 KB |
testcase_22 | AC | 2 ms
6,940 KB |
testcase_23 | WA | - |
ソースコード
/*** @file template.cpp* @brief 競技プログラミングのデッキ* @author Gex777* @date update:2023/04/21*/#include <iostream>#include <iomanip>#include <algorithm>#include <vector>#include <cmath>#include <set>#include <unordered_set>#include <map>#include <unordered_map>#include <string>#include <sstream>#include <climits>#include <bitset>#include <deque>#include <cassert>#include <list>#include <queue>#include <valarray>#include <complex>#include <bitset>#include <atcoder/all> //ACLusing namespace std;using namespace atcoder;// 独自型定義typedef long long ll;typedef unsigned long long ull;typedef vector<int> vi;typedef vector<vi> vvi;typedef vector<ll> vll;typedef vector<vll> vvll;typedef vector<vvll> vvvll;typedef vector<string> vs;typedef vector<char> vc;typedef vector<vc> vvc;typedef vector<bool> vb;typedef vector<vb> vvb;typedef vector<double> vd;typedef vector<vd> vvd;typedef long double ld;typedef pair<int, int> pii;typedef pair<ll, ll> pll;using AdjacencyList = map<int, vi>;using EdgeAdjacencyList = map<int, vector<int, int>>;// マクロの宣言#define all(x) x.begin(), x.end()// 定数宣言constexpr double PI = 3.141592653589793;constexpr ll MOD998 = 998244353;constexpr ll MOD107 = 1000000007;/*****************************************************************ここから下は自作ライブラリ******************************************************************/// コンテナの中身を表示, 1行で出力をする, debug用template <typename T>void printv(T &a){for (const auto &x : a){cout << x << " ";}puts("");return;}// コンテナの中身を表示, 二次元配列用template <typename T>void printvv(T &a){for (const auto &x : a){printv(x);}}// コンテナの中身を表示, pair型template <typename T>void print_vpair(const T &a){for (const auto &x : a){cout << "(" << x.first << ", " << x.second << "), ";}puts("");return;}template <class T>inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}template <class T>inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}// コンテナの中身を表示, 改行して出力をする, debug用template <typename T>void println(T &a){for (const auto &x : a){cout << x << endl;}return;}// 1~Nまでの総和を求めるll sum_from_1_to_N(ll N){if (N < 1LL){return 0;}if ((N & 1) == 0) // even{return N / 2 * (N + 1);}else // odd{return (N + 1) / 2 * N;}}// A~Nまでの総和を求めるll sum_from_A_to_B(ll A, ll B){return sum_from_1_to_N(B) - sum_from_1_to_N(A);}// a^bを求める, 繰り返し2乗法を用いる,3番目の引数はModを取る場合に設定ll intPowMod(ll a, ll b, const ll MOD = LLONG_MAX){ll ans = 1;ll A = a;while (b > 0){int n = b % 2;b /= 2;if (n == 1){ans *= A % MOD;ans %= MOD;}A = ((A % MOD) * (A % MOD)) % MOD;}return ans;}ld arg_to_rad(ld arg){return (arg * PI / 180.0);}ld rad_to_arg(ld rad){return rad * 180.0 / PI;}// C(n, m)を求めるll combination(const ll n, const ll m){assert(n >= m); // n>=mは保証されるll up = 1;ll down = 1;for (int i = n; i > n - m; i--){up *= i;}for (int i = m; i >= 2; i--){down *= i;}return up / down;}// 動的計画法で前処理,O(N**2)vvll combination_table(const int MAX_N = 50){vvll com = vvll(MAX_N + 1, vll(MAX_N + 1, 0)); // 前計算の結果を保存com[0][0] = 1;for (int i = 1; i <= MAX_N; ++i){com[i][0] = 1;for (int j = 1; j <= MAX_N; j++){com[i][j] = (com[i - 1][j - 1] + com[i - 1][j]);}}return com;}// a÷bをMODで割ったあまりを返す関数ll DivisionMod(ll a, ll b, ll MOD){return (a * intPowMod(b, MOD - 2, MOD)) % MOD;}// C(n, r)をModで割った余りを返す関数, 3番めの引数を入れないと通常のConbinationll combinationMod(ll n, ll r, ll MOD = LLONG_MAX){// 分子upを求めるll up = 1;for (ll i = n - r + 1; i <= n; ++i){up = (up * i) % MOD;}// 分母downを求めるll down = 1;for (ll i = 1; i <= r; ++i)down = (down * i) % MOD;return DivisionMod(up, down, MOD);}// a,bの最大公約数を求める, A>=B>=0の時, 計算量O(logB)long long GCD(long long a, long long b){if (b == 0)return a;elsereturn GCD(b, a % b);}// 拡張ユークリッドの互助法, 返り値: a と b の最大公約数// ax + by = gcd(a, b) を満たす (x, y) が格納されるlong long extGCD(long long a, long long b, long long &x, long long &y){if (b == 0){x = 1;y = 0;return a;}long long d = extGCD(b, a % b, y, x);y -= a / b * x;return d;}// 最小公倍数ll LCM(ll a, ll b){return a * b / GCD(a, b);}// 素数判定, P->true, not_P->falsebool check_Prime(ll N){if (N == 2)return true;if (N == 1 || (N & 1) == 0)return false;for (ll i = 3; i <= sqrt(N); i += 2){if (N % i == 0)return false;}return true;}// 素因数分解,key:素数, value:指数のmap<ll,ll>を返すmap<ll, ll> prime_factorize(ll number){map<ll, ll> table;for (ll i = 2; i * i <= number; ++i){while (number % i == 0){table[i]++;number /= i;}}if (number != 1LL){table[number]++;}return table;}/* エラストステネス and 高速素因数分解prime->IsPrime[i]=i; not prime ->最小の素因数 */vi Eratosthenes(size_t max_number){vi IsPrime(max_number + 1);// tableの初期化for (int i = 1; i < IsPrime.size(); ++i){IsPrime[i] = i;}for (int i = 2; i <= sqrt(max_number); ++i){for (int j = i; j <= max_number; j += i){if (IsPrime[j] == j){IsPrime[j] = i;}}}return IsPrime;}// O(N)でNの階乗を求めるll factorial(const ll N){ll ans = 1;for (ll i = 1; i <= N; ++i){ans *= i;}return ans;}// Run Length Encoding, ランレングス圧縮template <typename T>vector<pair<T, int>> RLE(const vector<T> &A){vector<pair<T, int>> rle;rle.push_back({A.front(), 1});for (int i = 1; i < A.size(); ++i){if (rle.back().first == A[i]){rle.back().second++;}else{rle.push_back({A[i], 1});}}return rle;}vector<pair<char, int>> RLE(const string &S){vector<pair<char, int>> rle;rle.push_back({S.front(), 1});for (int i = 1; i < S.size(); ++i){if (rle.back().first == S[i]){rle.back().second++;}else{rle.push_back({S[i], 1});}}return rle;}void DEBUG_INDICATE(){static int cnt = 0;cout << "-----DEBUG:" << cnt++ << "------" << endl;return;}/* RMQ:[0,n-1] について、区間ごとの最小値を管理する構造体update(i,x): i 番目の要素を x に更新。O(log(n))query(a,b): [a,b) での最小の要素を取得。O(log(n))*/template <typename T>struct RangeMinimumQuery{const T INF = numeric_limits<T>::max();int n; // 葉の数vector<T> dat; // 完全二分木の配列RangeMinimumQuery(int n_) : n(), dat(n_ * 4, INF){ // 葉の数は 2^x の形int x = 1;while (n_ > x){x *= 2;}n = x;}void update(int i, T x){i += n - 1;dat[i] = x;while (i > 0){i = (i - 1) / 2; // parentdat[i] = min(dat[i * 2 + 1], dat[i * 2 + 2]);}}// the minimum element of [a,b)T query(int a, int b) { return query_sub(a, b, 0, 0, n); }T query_sub(int a, int b, int k, int l, int r){if (r <= a || b <= l){return INF;}else if (a <= l && r <= b){return dat[k];}else{T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);return min(vl, vr);}}};/* RMQ:[0,n-1] について、区間ごとの最小値を管理する構造体update(i,x): i 番目の要素を x に更新。O(log(n))query(a,b): [a,b) での最小の要素を取得。O(log(n))*/template <typename T>struct RangeMaximumQuery{const T INF = numeric_limits<T>::min();int n; // 葉の数vector<T> dat; // 完全二分木の配列RangeMaximumQuery(int n_) : n(), dat(n_ * 4, INF){ // 葉の数は 2^x の形int x = 1;while (n_ > x){x *= 2;}n = x;}void update(int i, T x){i += n - 1;dat[i] = x;while (i > 0){i = (i - 1) / 2; // parentdat[i] = max(dat[i * 2 + 1], dat[i * 2 + 2]);}}// the minimum element of [a,b)T query(int a, int b) { return query_sub(a, b, 0, 0, n); }T query_sub(int a, int b, int k, int l, int r){if (r <= a || b <= l){return INF;}else if (a <= l && r <= b){return dat[k];}else{T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);return max(vl, vr);}}};// Union-Findstruct UnionFind{vector<int> par, rank, siz;// 構造体の初期化UnionFind(int n) : par(n, -1), rank(n, 0), siz(n, 1) {}// 根を求めるint root(int x){if (par[x] == -1)return x; // x が根の場合は x を返すelsereturn par[x] = root(par[x]); // 経路圧縮}// x と y が同じグループに属するか (= 根が一致するか)bool issame(int x, int y){return root(x) == root(y);}// x を含むグループと y を含むグループを併合するbool unite(int x, int y){int rx = root(x), ry = root(y); // x 側と y 側の根を取得するif (rx == ry)return false; // すでに同じグループのときは何もしない// union by rankif (rank[rx] < rank[ry])swap(rx, ry); // ry 側の rank が小さくなるようにするpar[ry] = rx; // ry を rx の子とするif (rank[rx] == rank[ry])rank[rx]++; // rx 側の rank を調整するsiz[rx] += siz[ry]; // rx 側の siz を調整するreturn true;}// x を含む根付き木のサイズを求めるint size(int x){return siz[root(x)];}};/* BIT: 区間和の更新や計算を行う構造体初期値は a_1 = a_2 = ... = a_n = 0計算量は全て O(logn)*/template <typename T>struct BIT{int n; // 配列の要素数(数列の要素数+1)vector<T> bit; // データの格納先// 構造体の初期化BIT(int n_) : n(n_ + 1), bit(n, 0) {}// add(i,x): a_i += x とするvoid add(int i, T x){for (int idx = i; idx < n; idx += (idx & -idx)){bit[idx] += x;}}// sum(i): a_1 + a_2 + ... + a_i を計算するT sum(int i){T s(0);for (int idx = i; idx > 0; idx -= (idx & -idx)){s += bit[idx];}return s;}};/**********************************************************ライブラリ終わり*****************************************************************/int main(){using mint = modint998244353;int N,K;cin >> N >> K;mint R = K;mint Q = N*(K-1);Q /= R.pow(N-1);cout << Q.val() << endl;}