#include<iostream> #include<vector> using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(0); ll n,m; ll modulo; cin>>n>>m>>modulo; vector<vector<vector<ll > > > dp(n+1); for(ll i=0 ; i<=n ; i++) { dp[i].resize(m+1); for(ll j=0 ; j<=m ; j++) { dp[i][j].resize(m+1,0); } } ll result=0; for(ll i=1 ; i<=m ; i++) for(ll j=i ; j<=m ; j++) dp[1][i][j]=1; for(ll k=2 ; k<=n ; k++) { // cout<<"K "<<k<<endl; for(ll i=1 ; i<=m ; i++) { for(ll j=i ; j<=m ; j++) { // cout<<"I "<<i<<" J "<<j<<endl; for(ll e=1 ; e<=j ; e++) { for(ll f=i ; f<=m ; f++) { dp[k][i][j]+=dp[k-1][e][f]%modulo; dp[k][i][j]%=modulo; } } // cout<<"VALUE "<<dp[k][i][j]<<endl; } } } for(ll i=1 ; i<=m ; i++) for(ll j=i ; j<=m ; j++) result=(result+dp[n][i][j])%modulo; cout<<result%modulo<<endl; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | #include<iostream> #include<vector> using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(0); ll n,m; ll modulo; cin>>n>>m>>modulo; vector<vector<vector<ll > > > dp(n+1); for(ll i=0 ; i<=n ; i++) { dp[i].resize(m+1); for(ll j=0 ; j<=m ; j++) { dp[i][j].resize(m+1,0); } } ll result=0; for(ll i=1 ; i<=m ; i++) for(ll j=i ; j<=m ; j++) dp[1][i][j]=1; for(ll k=2 ; k<=n ; k++) { // cout<<"K "<<k<<endl; for(ll i=1 ; i<=m ; i++) { for(ll j=i ; j<=m ; j++) { // cout<<"I "<<i<<" J "<<j<<endl; for(ll e=1 ; e<=j ; e++) { for(ll f=i ; f<=m ; f++) { dp[k][i][j]+=dp[k-1][e][f]%modulo; dp[k][i][j]%=modulo; } } // cout<<"VALUE "<<dp[k][i][j]<<endl; } } } for(ll i=1 ; i<=m ; i++) for(ll j=i ; j<=m ; j++) result=(result+dp[n][i][j])%modulo; cout<<result%modulo<<endl; return 0; } |