제출 #667286

#제출 시각아이디문제언어결과실행 시간메모리
667286ziduo캥거루 (CEOI16_kangaroo)Java
100 / 100
142 ms41488 KiB
import java.io.*;
import java.util.*;
public class kangaroo {
	static int[][] X;
	static int v;
	static int[][][] dp;
	public static void main(String[] args)throws IOException {
		// TODO Auto-generated method stub
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    int n = Integer.parseInt(st.nextToken());
	    int s = Integer.parseInt(st.nextToken());
	    int e = Integer.parseInt(st.nextToken());
	    long[][] dp = new long[n+1][n+1];
	    if(s>e) {
	    	int save = s;
	    	s = e;
	    	e = save;
	    }
	    long mod = 1000000007;
	    dp[1][1] = 1;
	    for(int i=2; i<=n; i++) {
	    	for(int j=1; j<=i; j++) {
	    		if(dp[i-1][j]==0)continue;
	    		if(i==s||i==e) {
	    			dp[i][j+1] = (dp[i][j+1]+dp[i-1][j])%mod;
	    			dp[i][j] = (dp[i][j]+dp[i-1][j])%mod;
	    			continue;
	    		}
	    		if(i<s) {
	    			dp[i][j+1] = (dp[i][j+1]+dp[i-1][j]*(j+1))%mod;
	    			dp[i][j-1] = (dp[i][j-1]+dp[i-1][j]*(j-1))%mod;
	    		}
	    		else if(i>s&&i<e) {
	    			dp[i][j+1] = (dp[i][j+1]+dp[i-1][j]*(j))%mod;
	    			dp[i][j-1] = (dp[i][j-1]+dp[i-1][j]*(j-1))%mod;	    			
	    		}
	    		else {
	    			dp[i][j+1] = (dp[i][j+1]+dp[i-1][j]*(j-1))%mod;
	    			dp[i][j-1] = (dp[i][j-1]+dp[i-1][j]*(j-1))%mod;	   	
	    		}
	    	}
	    }
	    System.out.println(dp[n][1]);
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...