题解

#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k; long long S;
cin >> n >> k >> S;
vector<long long> a(n);
for (auto &v : a) cin >> v;
// 阶乘（__int128 防溢出，> S 视为不可用）
vector<long long> fact(26, 1);
vector<char> factOK(26, 1);
__int128 v = 1;
for (int i = 1; i <= 25; i++) {
v *= i;
if (v > S) { fact[i] = 0; factOK[i] = 0; }
else fact[i] = (long long)v;
}
int n1 = n / 2, n2 = n - n1;
vector<pair<long long,int>> v1, v2;
auto genList = [&](int lo, int hi, vector<pair<long long,int>>& out) {
int len = hi - lo;
int total = 1;
for (int i = 0; i < len; i++) total *= 3;
for (int t = 0; t < total; t++) {
int x = t;
long long sum = 0; int cnt = 0;
bool ok = true;
for (int i = 0; i < len; i++) {
int st = x % 3; x /= 3;
if (st == 0) continue;
if (st == 1) {
if (a[lo + i] > S) { ok = false; break; }
sum += a[lo + i];
} else {
int idx = (int)a[lo + i];
if (idx > 25 || !factOK[idx]) { ok = false; break; }
sum += fact[idx]; cnt++;
}
if (sum > S) { ok = false; break; }
}
if (ok) out.push_back({sum, cnt});
}
};
genList(0, n1, v1);
genList(n1, n, v2);
sort(v2.begin(), v2.end()); // (sum, cnt)：同 sum 内 cnt 升序
long long ans = 0;
for (auto &p : v1) {
long long need = S - p.first;
if (need < 0) continue;
int maxCnt = k - p.second;
if (maxCnt < 0) continue;
auto lo = lower_bound(v2.begin(), v2.end(), make_pair(need, -1));
auto hi = upper_bound(v2.begin(), v2.end(), make_pair(need, maxCnt));
ans += hi - lo;
}
cout << ans << endl;
return 0;
}