QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#340175#1810. Generate the SequencesHKOI0#WA 19ms19428kbC++201.3kb2024-02-28 17:33:022024-02-28 17:33:02

Judging History

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

  • [2024-02-28 17:33:02]
  • 评测
  • 测评结果:WA
  • 用时:19ms
  • 内存:19428kb
  • [2024-02-28 17:33:02]
  • 提交

answer

#include <bits/stdc++.h>

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{

};
void solve() {
    int n,m;
    cin>>n>>m;
    vector dp(n+2,vector<ll>(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+1][j+1]+dp[i][j])%MOD;
            if(i-j<(ll)j*(m-2)) dp[i+1][j]=(dp[i+1][j]+dp[i][j]*(((ll)j*(m-2)%MOD-(i-j)+MOD)%MOD)%MOD)%MOD;
        }
    ll ans=0;
    for(int i=0;i<=n;i++) {
        ll sum=0;
        for(int j=0;j<=i;j++) sum=(sum+dp[i][j])%MOD;
        ans=(ans+sum*binom(n,i))%MOD;
    }
    cout<<ans<<'\n';
}

int32_t main() {
#ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    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;
#endif
    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
Wrong Answer
time: 19ms
memory: 19428kb

input:

2 3

output:

560943579

result:

wrong answer expected '5', found '560943579'