結果
問題 | No.3095 Many Min Problems |
ユーザー |
|
提出日時 | 2025-03-05 12:00:25 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 307 ms / 2,000 ms |
コード長 | 1,764 bytes |
コンパイル時間 | 8,637 ms |
コンパイル使用メモリ | 354,484 KB |
実行使用メモリ | 8,608 KB |
最終ジャッジ日時 | 2025-03-05 12:00:43 |
合計ジャッジ時間 | 15,223 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include "atcoder/math.hpp" #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using ll = long long; using pll = pair<ll, ll>; using pii = pair<int, int>; using mint = modint998244353; constexpr ll mod = 998244353; using MINT = modint1000000007; constexpr ll MOD = 1000000007; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; template <typename T> void print(vector<T> A); int main() { ios::sync_with_stdio(false); std::cin.tie(nullptr); int N, M; cin >> N >> M; //R^1+R^2+...R^Nを計算 auto Tohi = [&](mint R) { mint ret = R; ret *= -R.pow(N) + mint(1); ret/=-R+mint(1); return ret; }; mint ans=0; for (int X = 1; X <= M; X++) { if (X == 1) { for (int k = 1; k <= N; k++) { ans+=mint(M-1).pow(k-1)*mint(M).pow(N-k)*mint(N-k+1); } continue; } if (X == M) { for (int k = 1; k <= N; k++) { ans+=mint(M)*mint(M).pow(N-k); } continue; } mint r = mint(M - X + 1) / mint(M); mint keisu = (mint(M).pow(N) / mint(M - X)) / mint(mint(1) - r); mint Xans = -r.pow(N + 1) * keisu * Tohi(mint(M - X) / (mint(M) * r)); //cout<<(-Xans).val()<<endl; Xans +=keisu* Tohi(mint(M - X) / mint(M)); //cout<<Xans.val()<<endl; ans+=Xans*mint(X); } cout<<ans.val()<<endl; } template <typename T> void print(vector<T> A) { for (int i = 0; i < A.size() - 1; i++) { cout << A[i] << ' '; } cout << A[A.size() - 1] << endl; return; }