제출 #604956

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

kangaroo

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma,popcnt")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define gcd __gcd
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define rep(i, n) for (int i=0; i<(n); i++)
#define rep1(i, n) for (int i=1; i<=(n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl "\n"

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
template<typename T, typename cmp = less<T>>
using ordered_set = tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;

constexpr int N = 2005;
constexpr int MOD = 1e9 + 7;
int dp[2][N];

void sadd(int& a, int b) {if((a += b) >= MOD) a -= MOD;}
int mul(int a, int b) {return (a * 1LL * b) % MOD;}

int32_t main() {
    fastio;
    int n, s, f; cin >> n >> s >> f; --s, --f;
    int *prv = dp[0], *nxt = dp[1];
    size_t fuck = sizeof(dp[0]);
    prv[1] = 1;
    rep1(i, n - 1) {
        memset(nxt, 0, fuck);
        for(int j = 1; j <= i; j++) {
            if(i == s || i == f) {
                sadd(nxt[j], prv[j]);
                sadd(nxt[j + 1], prv[j]);
            }
            else {
                sadd(nxt[j + 1], mul(prv[j], j + 1 - (i > s) - (i > f)));
                sadd(nxt[j - 1], mul(prv[j], j - 1));
            }
        }
        swap(prv, nxt);
    }
    cout << prv[1] << endl;
}

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