Submission #940287

#	Time	Username	Problem	Language	Result	Execution time	Memory
940287		parlimoos	Kangaroo (CEOI16_kangaroo)	C++14	0 / 100	1 ms	348 KiB

kangaroo

//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

const int MOD = int(1e9) + 7;

int n , s , t;
int dp[2001][2001][4];
vector<int> a;

void Add(int &a , int b){
    a += b;
    if(a > MOD) a -= MOD;
    if(a < 0) a += MOD;
}
int Mul(int a , int b){
    return (1ll * a * b) % MOD;
}
int Pow(int a , int b){
    int res = 1;
    while(b){
        if((b & 1)) res = Mul(res , a);
        a = Mul(a , a) , b >>= 1;
    }
    return res;
}
int f(){
    dp[0][0][3] = 1;
    for(int i = 1 ; i <= n ; i++) if(i != s and i != t) a.pb(i);
    for(int i = 0 ; i < n - 2 ; i++){
        if(i == s or i == t) continue;
        for(int c = 0 ; c <= i ; c++){
            for(int md = 0 ; md < 4 ; md++){
                Add(dp[i + 1][c + 1][md] , Mul(c + 1 , dp[i][c][md]));
                if(c > 1) Add(dp[i + 1][c - 1][md] , Mul(c + 1 , dp[i][c][md]));
                if((md & 1)){
                    if(a[i] < s) Add(dp[i + 1][c + 1][md ^ 1] , dp[i][c][md]);
                    if(a[i] > s and c > 0) Add(dp[i + 1][c][md ^ 1] , dp[i][c][md]);
                }
                if(((md >> 1) & 1)){
                    if(a[i] < t) Add(dp[i + 1][c + 1][md ^ 2] , dp[i][c][md]);
                    if(a[i] > t and c > 0) Add(dp[i + 1][c][md ^ 2] , dp[i][c][md]);
                }
            }
        }
    }
    return dp[n - 2][1][0];
}

int main(){
    cin >> n >> s >> t;
    if(s > t) swap(s , t);
    if(n == 2) cout << 1;
    else if(n == 3){
        if((s == 1 and t == 3) or (s == 1 and t == 3)) cout << 0;
        else cout << 1;
    }else cout << f();
}

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