109912024-05-02 20:12:35szilBástyák törött sakktábláncpp17Hibás válasz 27/1004ms764 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll MOD = 1e9+7;
const int MAXN = 2001;

int v[MAXN];
ll fact[MAXN];

ll bpow(ll a, ll k) {
    if (k == 0) return 1;
    if (k & 1) return (a*bpow(a, k-1))%MOD;
    ll x = bpow(a, k/2);
    return (x*x)%MOD;
}

ll inv(ll x) {
    return bpow(x, MOD-2);
}

ll nck(ll a, ll b) {
    return (fact[a] * inv((fact[b] * fact[a-b]) % MOD)) % MOD;
}

/*
5
1 2 2 3 4
*/

ll calc(ll a, ll b) {
    if (a < b) swap(a, b);
    return (nck(a, b) * fact[b])%MOD;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    fact[0] = fact[1] = 1;
    for (ll i = 2; i < MAXN; i++) {
        fact[i] = (fact[i-1] * i) % MOD;
    }
    for (int i = 1; i <= n; i++) cin >> v[i];
    int cnt = 1;
    for (int i = 2; i <= n; i++) {
        if (v[i] == v[1]) cnt++;
        else break;
    }
    if (v[1] == v[n]) {
        cout << calc(v[1], n);
        return 0;
    }
    ll ans = 0;
    for (int i = 0; i <= min(n-cnt, v[1]); i++) {
        ll x = ((calc(v[1]-i, cnt) * calc(n-cnt-i, v[n]-v[1])) % MOD);
        if (v[1]-i > cnt && n-cnt-i > v[n]-v[1]) continue;
        x *= (((nck(v[1], i) * nck(n-cnt, i)) % MOD) * fact[i]) % MOD;
        x %= MOD;
        ans += x;
        ans %= MOD;
    }
    cout << ans << "\n";
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Hibás válasz2ms356 KiB
2Hibás válasz3ms356 KiB
subtask20/12
3Elfogadva3ms356 KiB
4Elfogadva3ms228 KiB
5Elfogadva3ms356 KiB
6Elfogadva3ms376 KiB
7Elfogadva3ms504 KiB
8Elfogadva2ms356 KiB
9Elfogadva3ms228 KiB
10Elfogadva3ms504 KiB
11Elfogadva3ms356 KiB
12Elfogadva3ms496 KiB
13Elfogadva3ms228 KiB
14Elfogadva3ms636 KiB
15Hibás válasz3ms508 KiB
16Hibás válasz3ms632 KiB
17Hibás válasz2ms376 KiB
18Hibás válasz3ms684 KiB
19Hibás válasz2ms228 KiB
20Hibás válasz3ms504 KiB
21Hibás válasz2ms376 KiB
subtask317/17
22Elfogadva3ms376 KiB
23Elfogadva3ms356 KiB
24Elfogadva3ms492 KiB
25Elfogadva3ms620 KiB
26Elfogadva3ms484 KiB
27Elfogadva3ms356 KiB
28Elfogadva3ms504 KiB
29Elfogadva3ms228 KiB
30Elfogadva3ms496 KiB
31Elfogadva3ms504 KiB
32Elfogadva3ms504 KiB
33Elfogadva3ms504 KiB
34Elfogadva3ms524 KiB
subtask40/20
35Elfogadva3ms508 KiB
36Elfogadva3ms392 KiB
37Elfogadva3ms536 KiB
38Elfogadva3ms496 KiB
39Elfogadva3ms504 KiB
40Elfogadva4ms408 KiB
41Elfogadva3ms504 KiB
42Elfogadva3ms504 KiB
43Elfogadva3ms360 KiB
44Elfogadva2ms356 KiB
45Elfogadva3ms492 KiB
46Elfogadva3ms492 KiB
47Hibás válasz3ms356 KiB
48Hibás válasz3ms376 KiB
49Hibás válasz2ms372 KiB
50Hibás válasz3ms360 KiB
51Hibás válasz3ms500 KiB
52Hibás válasz3ms504 KiB
53Hibás válasz3ms484 KiB
54Elfogadva2ms228 KiB
55Elfogadva3ms400 KiB
56Elfogadva3ms360 KiB
57Elfogadva3ms376 KiB
58Elfogadva3ms376 KiB
59Elfogadva3ms504 KiB
60Elfogadva3ms504 KiB
61Elfogadva3ms504 KiB
62Elfogadva3ms504 KiB
63Elfogadva3ms368 KiB
64Elfogadva3ms484 KiB
65Elfogadva4ms508 KiB
66Elfogadva3ms504 KiB
67Hibás válasz3ms356 KiB
68Hibás válasz3ms356 KiB
69Hibás válasz3ms504 KiB
70Hibás válasz3ms752 KiB
71Hibás válasz3ms368 KiB
72Hibás válasz3ms360 KiB
73Hibás válasz3ms360 KiB
subtask510/10
74Elfogadva3ms228 KiB
75Elfogadva3ms496 KiB
76Elfogadva3ms504 KiB
77Elfogadva3ms632 KiB
78Elfogadva2ms412 KiB
79Elfogadva2ms380 KiB
80Elfogadva4ms504 KiB
81Elfogadva3ms356 KiB
82Elfogadva3ms528 KiB
83Elfogadva3ms228 KiB
84Elfogadva3ms232 KiB
85Elfogadva3ms376 KiB
86Elfogadva3ms504 KiB
87Elfogadva3ms376 KiB
88Elfogadva3ms504 KiB
89Elfogadva4ms364 KiB
90Elfogadva4ms376 KiB
91Elfogadva4ms356 KiB
92Elfogadva3ms228 KiB
93Elfogadva4ms484 KiB
subtask60/41
94Hibás válasz3ms372 KiB
95Hibás válasz3ms508 KiB
96Elfogadva3ms356 KiB
97Elfogadva3ms228 KiB
98Elfogadva3ms648 KiB
99Elfogadva2ms228 KiB
100Elfogadva3ms372 KiB
101Elfogadva3ms632 KiB
102Elfogadva3ms356 KiB
103Elfogadva4ms228 KiB
104Elfogadva3ms404 KiB
105Elfogadva3ms356 KiB
106Elfogadva3ms632 KiB
107Elfogadva3ms360 KiB
108Hibás válasz2ms356 KiB
109Hibás válasz3ms504 KiB
110Hibás válasz3ms504 KiB
111Hibás válasz2ms356 KiB
112Hibás válasz3ms508 KiB
113Hibás válasz3ms504 KiB
114Hibás válasz3ms504 KiB
115Elfogadva3ms632 KiB
116Elfogadva3ms764 KiB
117Elfogadva3ms360 KiB
118Elfogadva2ms356 KiB
119Elfogadva3ms356 KiB
120Elfogadva3ms504 KiB
121Elfogadva3ms356 KiB
122Elfogadva3ms536 KiB
123Elfogadva3ms484 KiB
124Elfogadva3ms504 KiB
125Elfogadva3ms504 KiB
126Elfogadva3ms376 KiB
127Elfogadva3ms380 KiB
128Hibás válasz3ms228 KiB
129Hibás válasz3ms356 KiB
130Hibás válasz4ms504 KiB
131Hibás válasz3ms376 KiB
132Hibás válasz3ms376 KiB
133Hibás válasz3ms356 KiB
134Hibás válasz3ms356 KiB
135Elfogadva3ms376 KiB
136Elfogadva3ms356 KiB
137Elfogadva4ms484 KiB
138Elfogadva4ms356 KiB
139Elfogadva4ms308 KiB
140Elfogadva3ms356 KiB
141Elfogadva3ms504 KiB
142Hibás válasz3ms376 KiB
143Hibás válasz3ms504 KiB
144Hibás válasz3ms356 KiB
145Hibás válasz3ms356 KiB
146Hibás válasz3ms356 KiB
147Hibás válasz4ms504 KiB
148Hibás válasz3ms264 KiB
149Hibás válasz3ms504 KiB
150Hibás válasz3ms372 KiB
151Hibás válasz3ms368 KiB
152Hibás válasz3ms376 KiB