結果

問題 No.2951 Similar to Mex
ユーザー nouka28nouka28
提出日時 2024-04-03 17:19:01
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,467 bytes
コンパイル時間 5,226 ms
コンパイル使用メモリ 310,252 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-25 20:50:20
合計ジャッジ時間 16,906 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,816 KB
testcase_01 AC 4 ms
6,816 KB
testcase_02 AC 6 ms
6,816 KB
testcase_03 AC 5 ms
6,820 KB
testcase_04 AC 4 ms
6,816 KB
testcase_05 AC 5 ms
6,816 KB
testcase_06 AC 3 ms
6,820 KB
testcase_07 AC 3 ms
6,820 KB
testcase_08 AC 4 ms
6,816 KB
testcase_09 AC 4 ms
6,820 KB
testcase_10 AC 3 ms
6,820 KB
testcase_11 RE -
testcase_12 WA -
testcase_13 WA -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 AC 3 ms
6,816 KB
testcase_37 AC 3 ms
6,816 KB
testcase_38 AC 4 ms
6,816 KB
testcase_39 WA -
testcase_40 RE -
testcase_41 AC 3 ms
6,816 KB
testcase_42 RE -
testcase_43 WA -
testcase_44 RE -
権限があれば一括ダウンロードができます

ソースコード

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++){
        //mexがiとなるもの
        for(int j=0;j<=N;j++){
            for(int k=0;k<i;k++){
                //[l,r]と[0,x]の共通部分を求める
                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));
                    //M<=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