Submission #8522824

---

Source Code Expand

#include<iostream>
#include<iomanip>
#include<cassert>
#include<stdexcept>
#include<utility>
#include<functional>
#include<numeric>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<array>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<complex>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<bitset>
#include<memory>
using namespace std;
using ll=long long;

int main(){
    int N,K;
    ll M;
    cin>>N>>K>>M;

    vector<vector<ll>> pat(N+2,vector<ll>(N+2));
    pat[1][0]=1;
    for(int i=0;i<pat.size();i++){
        for(int j=0;j<pat[0].size();j++){
            if(j+1<pat[0].size()) (pat[i][j+1]+=pat[i][j]*i)%=M;
            if(i+1<pat.size()) (pat[i+1][j]+=pat[i][j])%=M;
        }
    }

    vector<vector<ll>> dp(K+1,vector<ll>(N+2));
    dp[0][1]=1;
    for(int i=0;i<K;i++){
        for(int j=0;j<=N+1;j++){
            for(int k=0;j+k<=N+1;k++){
                (dp[i+1][j+k]+=dp[i][j]*pat[j][k])%=M;
            }
        }
    }
    
    cout<<dp[K][N+1]<<endl;
    return 0;
}

Submission Info

Judge Result