Submission #318339

#	Time	Username	Problem	Language	Result	Execution time	Memory
318339		HPC	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	28 ms	31724 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN=2e3+5;
const ll MOD = 1e9+7;

int N, S, T;
ll dp[MAXN][MAXN];

int main(){
    cin >> N >> S >> T;
    if(S > T){
        swap(S,T);
    }
    if(N == 1){
        cout << "1\n";
        return 0;
    }
    dp[0][0] = 1;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(i == S || i == T){
                dp[i][j] = dp[i-1][j]+dp[i-1][j-1];
            }else if(i > T){
                dp[i][j] = (j-2)*dp[i-1][j-1]+j*dp[i-1][j+1];
            }else if(i > S){
                dp[i][j] = (j-1)*dp[i-1][j-1]+j*dp[i-1][j+1];
            }else{
                dp[i][j] = j*dp[i-1][j-1]+j*dp[i-1][j+1];
            }/*
            dp[i][j][0] = j*dp[i-1][j-1][0]+j*dp[i-1][j+1][0];
            dp[i][j][1] = (j-1)*dp[i-1][j-1][1]+j*dp[i-1][j+1][1]+2*dp[i-1][j][0]+2*dp[i-1][j-1][0];
            dp[i][j][2] = (j-2)*dp[i-1][j-1][2]+j*dp[i-1][j+1][2]+dp[i-1][j][1]+dp[i-1][j-1][1];*/
            dp[i][j] %= MOD;
        }
    }
    cout << dp[N][1] << '\n';
  	return 0;
}

/*
https://oj.uz/problem/view/CEOI16_kangaroo
A[i]>A[i-1] 
2 1 5 3 4
(N-2)!
*/

• Subtask 1: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 49 / 49