結果

問題 No.2951 Similar to Mex
ユーザー nouka28nouka28
提出日時 2024-04-03 21:16:58
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,308 bytes
コンパイル時間 5,205 ms
コンパイル使用メモリ 309,984 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-25 20:50:24
合計ジャッジ時間 16,795 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12 WA * 4 RE * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#include<atcoder/all>
using namespace atcoder;
using mint=atcoder::modint998244353;

mint dp[89][89][89];
mint binom[89][89];
int main(){
    int N,M,K;cin>>N>>M>>K;
    binom[0][0]=1;
    for(int i=0;i<85;i++){
        for(int j=0;j<85;j++){
            binom[i+1][j]+=binom[i][j];
            binom[i+1][j+1]+=binom[i][j];
        }
    }
    dp[1][N][0]=1;
    for(int i=1;i<=M+1;i++){
        for(int j=0;j<=N;j++){
            for(int k=0;k<i;k++){
                auto fit=[](int l,int r,int x)->int {
                    return x<l?0:min(r,x)-l+1;
                };
                if(i<=M){
                    for(int l=0;l<=j;l++){
                        if(l==0){
                            dp[i+1][j][0]+=dp[i][j][k]*mint(i).pow(fit(i-k,i,K));
                        }else{
                            dp[i+1][j-l][k+1]+=dp[i][j][k]*binom[j][l];
                        }
                    }
                }else{
                    if(j>0)continue;
                    mint tmp=dp[i][j][k]*mint(i).pow(fit(i-k,i,K));
                    for(int l=i+1;l<=K;l++){
                        tmp*=l;
                    }
                    dp[i+1][0][0]+=tmp;
                }
            }
        }
    }
    cout<<dp[M+2][0][0].val()<<endl;
}
0