109912024-05-02 20:12:35szilBástyák törött sakktábláncpp17Wrong answer 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Wrong answer2ms356 KiB
2Wrong answer3ms356 KiB
subtask20/12
3Accepted3ms356 KiB
4Accepted3ms228 KiB
5Accepted3ms356 KiB
6Accepted3ms376 KiB
7Accepted3ms504 KiB
8Accepted2ms356 KiB
9Accepted3ms228 KiB
10Accepted3ms504 KiB
11Accepted3ms356 KiB
12Accepted3ms496 KiB
13Accepted3ms228 KiB
14Accepted3ms636 KiB
15Wrong answer3ms508 KiB
16Wrong answer3ms632 KiB
17Wrong answer2ms376 KiB
18Wrong answer3ms684 KiB
19Wrong answer2ms228 KiB
20Wrong answer3ms504 KiB
21Wrong answer2ms376 KiB
subtask317/17
22Accepted3ms376 KiB
23Accepted3ms356 KiB
24Accepted3ms492 KiB
25Accepted3ms620 KiB
26Accepted3ms484 KiB
27Accepted3ms356 KiB
28Accepted3ms504 KiB
29Accepted3ms228 KiB
30Accepted3ms496 KiB
31Accepted3ms504 KiB
32Accepted3ms504 KiB
33Accepted3ms504 KiB
34Accepted3ms524 KiB
subtask40/20
35Accepted3ms508 KiB
36Accepted3ms392 KiB
37Accepted3ms536 KiB
38Accepted3ms496 KiB
39Accepted3ms504 KiB
40Accepted4ms408 KiB
41Accepted3ms504 KiB
42Accepted3ms504 KiB
43Accepted3ms360 KiB
44Accepted2ms356 KiB
45Accepted3ms492 KiB
46Accepted3ms492 KiB
47Wrong answer3ms356 KiB
48Wrong answer3ms376 KiB
49Wrong answer2ms372 KiB
50Wrong answer3ms360 KiB
51Wrong answer3ms500 KiB
52Wrong answer3ms504 KiB
53Wrong answer3ms484 KiB
54Accepted2ms228 KiB
55Accepted3ms400 KiB
56Accepted3ms360 KiB
57Accepted3ms376 KiB
58Accepted3ms376 KiB
59Accepted3ms504 KiB
60Accepted3ms504 KiB
61Accepted3ms504 KiB
62Accepted3ms504 KiB
63Accepted3ms368 KiB
64Accepted3ms484 KiB
65Accepted4ms508 KiB
66Accepted3ms504 KiB
67Wrong answer3ms356 KiB
68Wrong answer3ms356 KiB
69Wrong answer3ms504 KiB
70Wrong answer3ms752 KiB
71Wrong answer3ms368 KiB
72Wrong answer3ms360 KiB
73Wrong answer3ms360 KiB
subtask510/10
74Accepted3ms228 KiB
75Accepted3ms496 KiB
76Accepted3ms504 KiB
77Accepted3ms632 KiB
78Accepted2ms412 KiB
79Accepted2ms380 KiB
80Accepted4ms504 KiB
81Accepted3ms356 KiB
82Accepted3ms528 KiB
83Accepted3ms228 KiB
84Accepted3ms232 KiB
85Accepted3ms376 KiB
86Accepted3ms504 KiB
87Accepted3ms376 KiB
88Accepted3ms504 KiB
89Accepted4ms364 KiB
90Accepted4ms376 KiB
91Accepted4ms356 KiB
92Accepted3ms228 KiB
93Accepted4ms484 KiB
subtask60/41
94Wrong answer3ms372 KiB
95Wrong answer3ms508 KiB
96Accepted3ms356 KiB
97Accepted3ms228 KiB
98Accepted3ms648 KiB
99Accepted2ms228 KiB
100Accepted3ms372 KiB
101Accepted3ms632 KiB
102Accepted3ms356 KiB
103Accepted4ms228 KiB
104Accepted3ms404 KiB
105Accepted3ms356 KiB
106Accepted3ms632 KiB
107Accepted3ms360 KiB
108Wrong answer2ms356 KiB
109Wrong answer3ms504 KiB
110Wrong answer3ms504 KiB
111Wrong answer2ms356 KiB
112Wrong answer3ms508 KiB
113Wrong answer3ms504 KiB
114Wrong answer3ms504 KiB
115Accepted3ms632 KiB
116Accepted3ms764 KiB
117Accepted3ms360 KiB
118Accepted2ms356 KiB
119Accepted3ms356 KiB
120Accepted3ms504 KiB
121Accepted3ms356 KiB
122Accepted3ms536 KiB
123Accepted3ms484 KiB
124Accepted3ms504 KiB
125Accepted3ms504 KiB
126Accepted3ms376 KiB
127Accepted3ms380 KiB
128Wrong answer3ms228 KiB
129Wrong answer3ms356 KiB
130Wrong answer4ms504 KiB
131Wrong answer3ms376 KiB
132Wrong answer3ms376 KiB
133Wrong answer3ms356 KiB
134Wrong answer3ms356 KiB
135Accepted3ms376 KiB
136Accepted3ms356 KiB
137Accepted4ms484 KiB
138Accepted4ms356 KiB
139Accepted4ms308 KiB
140Accepted3ms356 KiB
141Accepted3ms504 KiB
142Wrong answer3ms376 KiB
143Wrong answer3ms504 KiB
144Wrong answer3ms356 KiB
145Wrong answer3ms356 KiB
146Wrong answer3ms356 KiB
147Wrong answer4ms504 KiB
148Wrong answer3ms264 KiB
149Wrong answer3ms504 KiB
150Wrong answer3ms372 KiB
151Wrong answer3ms368 KiB
152Wrong answer3ms376 KiB