結果

問題 No.3095 Many Min Problems
コンテスト
ユーザー autumn09
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0