Submission #1799877
Source Code Expand
import java.util.*; class Main { static final long MOD=1000000007; public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n=scan.nextInt(); int m=scan.nextInt(); long[][][]dp=new long[2][n][n]; dp[0][0][0]=1; for(int i=0;i<m;++i){ int u=i%2; for(int j=0;j<n;++j)Arrays.fill(dp[1-u][j],0); for(int j=0;j<n;++j) for(int k=0;k<n;++k){ if(j<n-1){ dp[1-u][j+1][k]+=dp[u][j][k]; dp[1-u][j+1][k]%=MOD; } dp[1-u][j][j]+=(k+1)*dp[u][j][k]; dp[1-u][j][j]%=MOD; dp[1-u][j][k]+=(j-k)*dp[u][j][k]; dp[1-u][j][k]%=MOD; } } long t=0; for(int i=0;i<n;++i) t=(t+dp[m%2][i][n-1])%MOD; for(int i=1;i<=n-1;++i) t=t*i%MOD; System.out.println(t); } }
Submission Info
Submission Time | |
---|---|
Task | F - Road of the King |
User | kirika_comp |
Language | Java8 (OpenJDK 1.8.0) |
Score | 1000 |
Code Size | 1052 Byte |
Status | AC |
Exec Time | 454 ms |
Memory | 25516 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 | 94 ms | 21844 KB |
01-02.txt | AC | 94 ms | 20564 KB |
01-03.txt | AC | 95 ms | 18900 KB |
01-04.txt | AC | 116 ms | 22856 KB |
01-05.txt | AC | 105 ms | 19924 KB |
01-06.txt | AC | 165 ms | 21292 KB |
01-07.txt | AC | 433 ms | 23500 KB |
01-08.txt | AC | 453 ms | 22260 KB |
01-09.txt | AC | 454 ms | 22604 KB |
01-10.txt | AC | 454 ms | 25516 KB |
sample-01.txt | AC | 92 ms | 19796 KB |
sample-02.txt | AC | 219 ms | 23360 KB |
sample-03.txt | AC | 301 ms | 25272 KB |