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