제출 #764760

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

kangaroo

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

void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }

#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif

using ll = long long;
using ld = long double;
using pii = pair<ll,ll>;

#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second

template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
	cout << "["; 
	for (auto it = v.begin(); it != v.end();) {
		cout << *it;
		if (++it != v.end()) cout << ", ";
	}
	return cout << "]";
}

//var 
ll T;

const ll MOD = 1e9 + 7;
struct mint {
    int x;
    mint() : x(0) {}
    template <class T> mint(T value) : x(value % MOD) { if (x < 0) x += MOD; }
    mint & operator+=(const mint &oth) { x += oth.x; if (x >= MOD) x -= MOD; return *this; }
    mint & operator-=(const mint &oth) { x -= oth.x; if (x < 0) x += MOD; return *this; }
    mint & operator*=(const mint &oth) { x = (long long) x * oth.x % MOD; return *this; }
    friend mint operator+(mint l, const mint &r) { return l += r; }
    friend mint operator-(mint l, const mint &r) { return l -= r; }
    friend mint operator*(mint l, const mint &r) { return l *= r; }
    mint & operator--() { if (--x == -1) x = MOD - 1; return *this; }
    mint & operator++() { if (++x == MOD) x = 0; return *this; }
    mint operator--(int) { mint temp = *this; --*this; return temp; }
    mint operator++(int) { mint temp = *this; ++*this; return temp; }
    mint operator-() const { return 0 - *this; }
    mint operator+() const { return *this; }
    friend bool operator==(const mint &l, const mint &r) { return l.x == r.x; }
    friend bool operator!=(const mint &l, const mint &r) { return l.x != r.x; }
    friend ostream & operator<<(ostream &out, const mint &a) { return out << a.x; }
    mint pow(long long e = MOD - 2) const {
        mint ans = 1, b = *this;
        while (e > 0) {
            if (e % 2 == 1) {
                ans *= b;
            }
            b *= b;
            e /= 2;
        }
        return ans;
    }
};

void solve() {
	ll n, x, y;
	cin >> n >> x >> y;
	x--, y--;

	vector<mint> dp(n + 1, 0);
	dp[0] = 1;

	ll seen_ends = 0;
	F0R (i, n) {
		vector<mint> new_dp(n + 1, 0);
		for (int num_comps = 0; num_comps <= n; num_comps++) if (dp[num_comps] != 0) {
			mint p = dp[num_comps];
			if (i == x or i == y) {
				if (num_comps != 0) new_dp[num_comps] += p;
				new_dp[num_comps + 1] += p;
			} else {
				// individual options
				{
					ll num_options = num_comps + 1 - seen_ends;
					new_dp[num_comps + 1] += p * num_options;
				}

				if (num_comps >= 2) {
					// merge components
					ll num_options = num_comps - 1;
					new_dp[num_comps - 1] += p * num_options;
				}
			}
		}
		if (i == x) seen_ends++;
		if (i == y) seen_ends++;
		swap(dp, new_dp);
	}

	cout << dp[1] << "\n";
}

int main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0);

	T = 1;
	//cin >> T;
	FOR(t, T)
		solve();

	cout.flush();
	return 0;
}

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