結果

問題 No.2801 Unique Maximum
ユーザー TeaDose
提出日時 2024-06-28 23:06:19
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,201 bytes
コンパイル時間 2,124 ms
コンパイル使用メモリ 171,872 KB
実行使用メモリ 13,888 KB
最終ジャッジ日時 2024-06-28 23:06:27
合計ジャッジ時間 7,266 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1
other -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
typedef long long ll;
const int N = 2e5;
const ll mod = 998244353;
ll fact[N+1], inv[N+1];
ll binpow(ll x, ll n){
    ll res = 1;
    while(n){
        if(n&1)res=(x*res)%mod;
        x=(x*x)%mod;
        n/=2;
    }
    return(res);
}
ll choose(int n, int k){
    if(n<k)return(0);
    return(fact[n]*inv[k]%mod*inv[n-k]%mod)%mod;
}
void solve(){
    ll n, m; cin >> n >> m;
    vector<ll> dp(n+1);
    dp[1]=1;
    ll ans = 0;
    for(int z=0; z<n-1; z++){
        ans=(ans+dp[n]*choose(m, z+1))%mod;
        vector<ll> dp2(n+1);
        for(int i=1; i<=n; i++){
            if(!dp[i])continue;
            for(int j=1; j<=min(i+1ll, n-i); j++){
                dp2[i+j]=(dp2[i+j]+dp[i]*choose(i+1, j))%mod;
            }
        }
        swap(dp, dp2);
    }
    ans=(ans+dp[n]*choose(m, n))%mod;
    cout << ans;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    fact[0]=1;
    for(int i=1; i<=N; i++)fact[i]=(fact[i-1]*i)%mod;
    inv[N]=binpow(fact[N], mod-2);
    for(int i=N; i>0; i--)inv[i-1]=(inv[i]*i)%mod;
    solve();
    return 0;
}
0