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 |
|
|
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 |