Submission #878973

#TimeUsernameProblemLanguageResultExecution timeMemory
878973Youssif_ElkadiMagneti (COCI21_magneti)C++17
0 / 110
1083 ms856 KiB
#include <bits/stdc++.h> using namespace std; const long long N = 1e4 + 5, mod = 1e9 + 7; long long fac[N], inv[N]; long long n, l; long long fp(long long base, long long power) { long long ret = 1; while (power) { if (power & 1) ret = (ret * base) % mod; power >>= 1; base = (base * base) % mod; } return ret; } long long ncr(long long nn, long long rr) { if (rr > nn || rr < 0) return 0; return ((fac[nn] * inv[rr]) % mod * inv[nn - rr]) % mod; } int main() { ios_base::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL); cin >> n >> l; vector<pair<int, long long>> arr(n); for (int i = 0; i < n; i++) cin >> arr[i].first, arr[i].second = i; fac[0] = fac[1] = 1; for (long long i = 2; i <= l; i++) fac[i] = (i * fac[i - 1]) % mod; inv[l] = fp(fac[l], mod - 2); for (long long i = l - 1; i >= 0; i--) inv[i] = (inv[i + 1] * (i + 1)) % mod; sort(arr.begin(), arr.end()); long long ans = 0; if (arr[0] == arr[n - 1]) return (ncr(l - (n - 1) * arr[0].first, l - n - (n - 1) * arr[0].first) * fac[n]) % mod; do { int boxes = l - n; for (int i = 1; i < n; i++) boxes -= max(arr[i - 1].first - 1, arr[i].first - 1); ans = (ans + ncr(n + boxes, boxes)) % mod; } while (next_permutation(arr.begin(), arr.end())); cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...