Cerinta completa

Let’s consider a permutation P = {p1, p2, …, pN} of the set of N = {1, 2, 3, …, N} elements .

P is called a magic set if it satisfies both of the following constraints:

  • Given a set of K integers, the elements in positions a1, a2, …, aK are less than their adjacent elements, i.e., pai-1 > pai < pai+1
  • Given a set of L integers, elements in positions b1, b2, …, bL are greater than their adjacent elements, i.e., pbi-1 < pbi > pbi+1

How many such magic sets are there?

Input Format
The first line of input contains three integers N, K, L separated by a single space.
The second line contains K integers, a1, a2, … aK each separated by single space.
the third line contains L integers, b1, b2, … bL each separated by single space.

Output Format
Output the answer modulo 1000000007 (109+7).

Constraints
3 <= N <= 5000
1 <= K, L <= 5000
2 <= ai, bj <= N-1, where i ∈ [1, K] AND j ∈ [1, L]

Sample Input #00 

4 1 1
2
3

Sample Output #00 

5

Explanation #00

Here, N = 4 a1 = 2 and b1 = 3. The 5 permutations of {1,2,3,4} that satisfy the condition are

  • 2 1 4 3
  • 3 2 4 1
  • 4 2 3 1
  • 3 1 4 2
  • 4 1 3 2

Sample Input #01

10 2 2
2 4
3 9

Sample Output #01

161280

Limbajul de programare folosit: cpp20

Cod:

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

static const long long MOD = 1000000007LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k, l;
    cin >> n >> k >> l;

    vector<int> a(n + 2, 0), b(n + 2, 0);
    for (int i = 0; i < k; i++) {
        int x;
        cin >> x;
        a[x] = 1;
    }
    for (int i = 0; i < l; i++) {
        int x;
        cin >> x;
        b[x] = 1;
    }

    for (int i = 1; i < n; i++) {
        if (a[i] && b[i]) {
            cout << 0 << '\n';
            return 0;
        }
        if ((a[i - 1] && a[i]) || (b[i - 1] && b[i])) {
            cout << 0 << '\n';
            return 0;
        }
    }

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

    for (int i = 2; i <= n; i++) {
        // Position i-1 must be a local minimum if a[i-1] is constrained,
        // and position i must not be forced local maximum.
        if (!(a[i - 1] || b[i])) {
            long long prefix = 0;
            for (int j = 1; j <= i; j++) {
                dp[i][j] = (dp[i][j] + prefix) % MOD;
                prefix += dp[i - 1][j];
                if (prefix >= MOD) prefix -= MOD;
            }
        }

        // Position i-1 must be a local maximum if b[i-1] is constrained,
        // and position i must not be forced local minimum.
        if (!(b[i - 1] || a[i])) {
            long long suffix = 0;
            for (int j = i; j >= 1; j--) {
                dp[i][j] = (dp[i][j] + suffix) % MOD;
                suffix += dp[i - 1][j - 1];
                if (suffix >= MOD) suffix -= MOD;
            }
        }
    }

    long long ans = 0;
    for (int j = 1; j <= n; j++) {
        ans += dp[n][j];
        if (ans >= MOD) ans -= MOD;
    }

    cout << ans << '\n';
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464641000

Link challenge: https://www.hackerrank.com/challenges/extremum-permutations/problem

Extremum Permutations