Submission #5376997
Source Code Expand
#include <bits/stdc++.h> const int INF=1e9,MOD=1e9+7; const long long LINF=1e18; using namespace std; #define int long long //template int dp[305][305][305]; int pw(int n,int k){ int res=1; while(k){ if(k&1)res*=n;res%=MOD; n*=n;n%=MOD; k>>=1; } return res; } //main signed main(){ int N,M;cin>>N>>M; memset(dp,0,sizeof(dp)); dp[0][N-1][1]=1; for(int i=0;i<M;i++){ for(int j=0;j<=N;j++){ for(int k=0;k<=N;k++){ if(j)dp[i+1][j-1][k]+=dp[i][j][k]*j; dp[i+1][j][N-j]+=dp[i][j][k]*k; dp[i+1][j][k]+=dp[i][j][k]*(N-j-k); if(j)dp[i+1][j-1][k]%=MOD; dp[i+1][j][N-j]%=MOD; dp[i+1][j][k]%=MOD; } } } cout<<dp[M][0][N]<<endl; }
Submission Info
Submission Time | |
---|---|
Task | F - Road of the King |
User | drogskol |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 753 Byte |
Status | AC |
Exec Time | 261 ms |
Memory | 221952 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 | 55 ms | 221952 KB |
01-02.txt | AC | 55 ms | 221952 KB |
01-03.txt | AC | 55 ms | 221952 KB |
01-04.txt | AC | 57 ms | 221952 KB |
01-05.txt | AC | 56 ms | 221952 KB |
01-06.txt | AC | 76 ms | 221952 KB |
01-07.txt | AC | 247 ms | 221952 KB |
01-08.txt | AC | 258 ms | 221952 KB |
01-09.txt | AC | 260 ms | 221952 KB |
01-10.txt | AC | 261 ms | 221952 KB |
sample-01.txt | AC | 55 ms | 221952 KB |
sample-02.txt | AC | 110 ms | 221952 KB |
sample-03.txt | AC | 158 ms | 221952 KB |