結果
問題 | No.1552 Simple Dice Game |
ユーザー |
![]() |
提出日時 | 2021-06-18 22:19:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 172 ms / 2,500 ms |
コード長 | 2,226 bytes |
コンパイル時間 | 1,041 ms |
コンパイル使用メモリ | 105,088 KB |
最終ジャッジ日時 | 2025-01-22 09:25:07 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 20 |
ソースコード
#include <algorithm>#include <cmath>#include <iomanip>#include <iostream>#include <map>#include <queue>#include <set>#include <string>#include <tuple>#include <vector>#define mkp make_pair#define mkt make_tuple#define rep(i, n) for (int i = 0; i < (n); ++i)#define all(v) v.begin(), v.end()using namespace std;typedef long long ll;// const ll MOD = 1e9 + 7;const ll MOD = 998244353;template <class T>void chmin(T &a, const T &b) {if (a > b) a = b;}template <class T>void chmax(T &a, const T &b) {if (a < b) a = b;}ll mod_pow(ll x, ll n) {x %= MOD;ll res = 1;while (n > 0) {if (n & 1) res = res * x % MOD;x = x * x % MOD;n >>= 1;}return res;}ll mod_inverse(ll x) {return mod_pow(x, MOD - 2);}void add(ll &a, ll b) {a = (a + b) % MOD;}void mul(ll &a, ll b) {a %= MOD;b %= MOD;a = a * b % MOD;}void solve() {ll N, M;cin >> N >> M;ll ans = 0;{ // maxll pre_value = 1;mul(pre_value, N);add(ans, pre_value);for (ll k = 2; k <= M; k++) {ll nex_value = 1;ll base = k * (k + 1) / 2;base %= MOD;mul(nex_value, base);mul(nex_value, N);mul(nex_value, mod_pow(k, (N - 1) % (MOD - 1)));ll res = nex_value;add(res, MOD - pre_value);mul(res, k);add(ans, res);pre_value = nex_value;}}{ // minll pre_value = 1;mul(pre_value, N % MOD * M % MOD);add(ans, MOD - pre_value * M % MOD);for (ll k = M - 1; k >= 1; k--) {ll nex_value = 1;ll base = (M - k + 1) * (k + M) / 2;base %= MOD;mul(nex_value, base);mul(nex_value, N);mul(nex_value, mod_pow(M - k + 1, (N - 1) % (MOD - 1)));ll res = nex_value;add(res, MOD - pre_value);mul(res, k);add(ans, MOD - res);pre_value = nex_value;}}cout << ans << endl;}int main() {cin.tie(nullptr);ios::sync_with_stdio(false);solve();return 0;}