Submission #1325701

#TimeUsernameProblemLanguageResultExecution timeMemory
1325701perchutsKangaroo (CEOI16_kangaroo)C++20
51 / 100
2105 ms242480 KiB
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int ll
//#define gato

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 3e5+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

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

int rnd(int l, int r) {
    uniform_int_distribution<int> uid(l, r);
    return uid(rng);
}

int dp[2005], ncr[2005][2005];

int n3(int n, int a, int b) {
    if (n == 2) return 1;
    if (a > b) swap(a, b);
    vector f(n+1, vector(n+1, vector(2, 0LL)));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            if (i == 1) {
                f[i][i][1] = 1;
                continue;
            }
            // f[i][j][0] = \sum f[i-1][k][1], k < j
            for (int k = 1; k < j; ++k) f[i][j][0] += f[i-1][k][1];
            f[i][j][0] %= mod;
            for (int k = j+1; k <= i; ++k) f[i][j][1] += f[i-1][k-1][0];
            f[i][j][1] %= mod;
        }
    }
    if (b == n) return (f[n-1][a][0] + f[n-1][a][1]) % mod;
    int ans = 0;
    for (int s1 = 1; s1 <= n-2; ++s1) {
        int s2 = n-1-s1;
        for (int i1 = 1; i1 <= min(a, s1); ++i1) {
            for (int i2 = 0; i1 + i2 <= s1 and i2 < b-a; ++i2) {
                int j = b-i1-i2;
                if (j > s2) continue;
                int ways = ncr[a-1][i1-1] * ncr[b-a-1][i2] % mod * ncr[n-1-b][s2-j] % mod;
                if (n & 1) ways = ways * ((f[s1][i1][0] * f[s2][j][0]) % mod + (f[s1][i1][1] * f[s2][j][1]) % mod) % mod;
                else ways = ways * ((f[s1][i1][1] * f[s2][j][0]) % mod + (f[s1][i1][0] * f[s2][j][1]) % mod) % mod;
                ans = (ans + ways) % mod;
            }
        }
    }
    return ans;
}

void solve() {
    int n, a, b; cin >> n >> a >> b;
    // dp[direcao][round][posicao]
    // quero fazer uma inclusao exclusao mesmo? acho que nao!
    dp[1] = 1;
    for (int i = 2; i <= n; ++i) {
        dp[i] = max(1LL, n-i) * dp[i-1] % mod;
        for (int j = 3; j < i; ++j) {
            int ways = ncr[n-i+j-(i!=n)][j] * dp[i-j] % mod;
            if (j & 1) dp[i] = (dp[i] + ways) % mod;
            else dp[i] = (dp[i] + mod - ways) % mod;
        }
        int livres = n - a - (b > a);
        if (i-1 <= livres and i != 2) {
            if (i & 1) dp[i] = (dp[i] + mod - ncr[livres][i-1]) % mod;
            else dp[i] = (dp[i] + ncr[livres][i-1]) % mod;
        }
    }
}

int brute(int n, int a, int b) {
    vector<int> p(n);
    iota(all(p), 1);
    int ans = 0;
    do {
        bool ok = (p[0] == a and p[n-1] == b);
        for (int i = 2; i < n; ++i) ok &= (p[i] < p[i-1]) != (p[i-1] < p[i-2]);
        if (ok) ans++;
    } while(next_permutation(all(p)));
    return ans;
}

int32_t main() {_
    for (int i = 0; i <= 2000; ++i) for (int j = 0; j <= i; ++j) {
        if (j == 0 or j == i) ncr[i][j] = 1;
        else ncr[i][j] = (ncr[i-1][j] + ncr[i-1][j-1]) % mod;
    }
#ifndef gato
    int n, a, b; cin >> n >> a >> b;
    //cout << brute(n, a, b) << endl;
    cout << n3(n, a, b) << endl;
#else
    int t = 1;
    while (true) {
        int n = rnd(2, 10), a = rnd(1, n-1), b = rnd(a+1, n);
        int my = n3(n, a, b), ans = brute(n, a, b);
        if (my != ans) {
            cout << "Wrong answer on test " << t << endl;
            cout << n << " " << a << " " << b << endl;
            cout << "Solve: " << my << endl;
            cout << "Brute: " << ans << endl;
            exit(0);
        }
        cout << "Accepted on test " << t++ << endl;
    }
#endif
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...