Submission #3606467


Source Code Expand

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD=1e9+7;
ll powmod(ll a, ll k){
    ll ap=a, ans=1;
    while(k>0){
        if(k%2==1){
            ans*=ap;
            ans%=MOD;
        }
        ap=ap*ap;
        ap%=MOD;
        k/=2;
    }
    return ans;
}
ll inv(ll a){
	return powmod(a, MOD-2);
}
int main()
{
	ll dp[301][301]={};
  ll s[301][301]={};
  ll f[301], invf[301];
  f[0]=1;
  for(ll i=1; i<=300; i++){
    f[i]=f[i-1]*i%MOD;
  }
  invf[300]=inv(f[300]);
  for(ll i=299; i>=0; i--){
    invf[i]=invf[i+1]*(i+1)%MOD;
  }
  ll comb[301][301];
  for(int i=0; i<=300; i++){
    for(int j=0; j<=i; j++){
      comb[i][j]=f[i]*invf[j]%MOD*invf[i-j]%MOD;
    }
  }
  int n, m; cin>>n>>m;
	fill(dp[1], dp[1]+m+1, 1);
  for(ll i=2; i<=n; i++){
    dp[i][i]=f[i-1];
    for(ll j=i+1; j<=m; j++){
      dp[i][j]=i*dp[i][j-1]%MOD;
      for(ll x=1; x<=i-1; x++){
        for(ll y=x-1; y<=min(j-2, j-i+x); y++){
          dp[i][j]+=(comb[i-1][x]*x%MOD*dp[x][y]%MOD*dp[i-x][j-1-y]%MOD);
          dp[i][j]%=MOD;
        }
      }
    }
  }
  cout<<dp[n][m]<<endl;
	return 0;
}

Submission Info

Submission Time
Task F - Road of the King
User chocorusk
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 1422 Byte
Status AC
Exec Time 2204 ms
Memory 1664 KB

Judge Result

Set Name sample all
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 3
AC × 16
Set Name Test Cases
sample sample-01.txt, sample-02.txt, sample-03.txt
all sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt AC 2 ms 1664 KB
01-02.txt AC 2 ms 1664 KB
01-03.txt AC 2 ms 1664 KB
01-04.txt AC 2 ms 1664 KB
01-05.txt AC 15 ms 1664 KB
01-06.txt AC 738 ms 1664 KB
01-07.txt AC 2174 ms 1664 KB
01-08.txt AC 2204 ms 1664 KB
01-09.txt AC 2203 ms 1664 KB
01-10.txt AC 2203 ms 1664 KB
sample-01.txt AC 2 ms 1664 KB
sample-02.txt AC 1492 ms 1664 KB
sample-03.txt AC 144 ms 1664 KB