QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#340174#1810. Generate the SequencesHKOI0#RE 0ms0kbC++202.1kb2024-02-28 17:32:232024-02-28 17:32:23

Judging History

你现在查看的是最新测评结果

  • [2024-02-28 17:32:23]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-02-28 17:32:23]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
using ll = long long;

const int N = 2e6 + 11;
const int MOD = 998244353;
int fa[N], fi[N];

int pm(int a, int b){
    if (b == 0) return 1;
    return pm(a * a % MOD, b / 2) * (b % 2 ? a : 1) % MOD;
}
int mi(int a){
    return pm(a, MOD - 2);
}

int binom(int n, int r){
    return fa[n] * fi[r] % MOD * fi[n - r] % MOD;
}

template<int MOD = 998244353>
struct Mint{
    int value;
    Mint() : value(0) {};
    Mint(int value) : value(value) { value = (value % MOD + MOD) % MOD; };
    Mint operator+ (const Mint& o) const { int res = value + o.value; return res >= MOD ? res - MOD : res; }
    Mint operator+= (const Mint& o) { *this = *this + o; }
    Mint operator- (const Mint& o) const { int res = value - o.value; return res < 0 ? res + MOD : res; }
    Mint operator* (const Mint& o) const { int res = value * o.value % MOD; return res; }
    Mint operator/ (const Mint& o) const { return *this * o.inv(); }
    Mint inv() const { return mi(value); }
    friend ostream& operator<< (ostream& out, const Mint& m) {
        return cout << m.value;
    }
};

using Zn = Mint<MOD>;
void solve() {
    int n,m;
    cin>>n>>m;
    vector dp(n+2,vector<Zn>(n+2));
    dp[0][0] = 1;
    for(int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            dp[i + 1][j + 1] += dp[i][j];
            if (i - j < j * (m - 2)) {
                dp[i + 1][j] += dp[i][j] * (Zn(j) * Zn(m - 2) - Zn(i - j));
            }
        }
    }
    Zn ans = 0;
    for(int i = 0; i <= n; i++) {
        Zn sum = 0;
        for (int j = 0; j <= i; j++) {
            sum += dp[i][j];
        }
        ans += sum * Zn(binom(n,i));
    }
    cout << ans << '\n';
}

int32_t main() {
#ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    fa[0] = 1; for (int i = 1; i < N; i++) fa[i] = fa[i - 1] * i % MOD;
    fi[N - 1] = mi(fa[N - 1]); for (int i = N - 2; i >= 0; i--) fi[i] = fi[i + 1] * (i + 1) % MOD;
    int T = 1;
    // cin >> T;
    while (T--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

2 3

output:


result: