제출 #683394

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
683394		Mkswll	캥거루 (CEOI16_kangaroo)	C++17	6 / 100	2 ms	596 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, int> pli;
typedef pair <int, ll> pil;
typedef pair <ll, ll> pll;
typedef pair <ld, ld> pdd;
#define cio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define cases int _; cin >> _; while(_--)
#define pb push_back
#define eb emplace_back
#define space << " " <<
#define lb lower_bound
#define ub upper_bound
#define F first
#define S second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define Unique(v) v.erase(unique(all(v)), v.end())
#define mset(x) memset(x, 0, sizeof(x))
#define sflush fflush(stdout)
#define cflush cout.flush()
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define nl cout << "\n";
#define binary(len, num) bitset <len> (num)
#define vt vector
#define ar array
#define Mat vt <vt <int> >

template <typename T> istream& operator >> (istream& in, vector<T>& a) {for(auto &x : a) in >> x; return in;};
template <typename T> ostream& operator << (ostream& out, vector<T>& a) {for(auto &x : a) out << x << ' '; return out;};

int read(){
    int w = 1, c, ret;
    while((c = getchar()) > '9' || c < '0'){
        w = (c == '-' ? -1 : 1);
    }
    ret = c - '0';
    while((c = getchar()) >= '0' && c <= '9'){
        ret = ret * 10 + c - '0';
    }
    return ret * w;
}

int rd(){
	int in;
	cin >> in;
	return in;
}
 
void write(int x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9){
        write(x / 10);
    }
    putchar(x % 10 + '0');
}

const int MAXN = 2e3 + 5, MAXM = 2e5 + 5, INF = 1e9 + 5, MOD = 1e9 + 7;
const ll LINF = 1e18 + 5;
const ld ep = 1e-8, Pi = acos(-1.0);

int n, m, k, x; 
int cs, cf;
int a[MAXN];
string s;

ll dp[MAXN][1005][2];

ll dfs(int cur, int stat, bool dir){
	if(stat == (1 << n) - 1) return cur == cf;
	if(dp[cur][stat][dir]) return dp[cur][stat][dir];
	ll ret = 0;
	if(dir){
		for(int i = 0; i < cur; ++i){
			if(!((1 << i) & stat)){
				ret += dfs(i, stat | (1 << i), dir ^ 1);
				ret %= MOD;
			}
		}
	}
	else{
		for(int i = cur + 1; i < n; ++i){
			if(!((1 << i) & stat)){
				ret += dfs(i, stat | (1 << i), dir ^ 1);
				ret %= MOD;
			}
		}
	}
	return dp[cur][stat][dir] = ret;
}





void clear(){
    
}

int main(){
    cio;
    cin >> n >> cs >> cf;
    --cs;
    --cf;
    cout << (dfs(cs, 1 << (cs), 0) + dfs(cs, 1 << (cs), 1)) % MOD;
    return 0;
}   

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