Problem Info
My Work
#include <iostream>
#include <vector>
#include <algorithm>
#include "debugging.h"
using std::cout;
using std::endl;
using std::vector;
constexpr int MOD = 1e9 + 7;
constexpr int MAX_SIZE = 1e5;
constexpr int MAX_TUPLE = 1e2;
long long pow_mod(long long base, long long exp) {
base %= MOD;
long long result = 1;
while (exp > 0) {
if (exp % 2 == 1) // if n is odd
result = result * base % MOD;
base = base * base % MOD;
exp /= 2; // divide by two
}
return result;
}
long long mod_inv(long long n) { // sauce is same as above
return pow_mod(n, MOD - 2);
}
// https://codeforces.com/problemset/problem/1462/E2 (input ommitted due to length)
int main() {
vector<vector<long long>> choose_table(MAX_SIZE + 1, vector<long long>(MAX_TUPLE + 1));
for (int s = 0; s <= MAX_SIZE; s++) {
long long curr = 1;
for (int t = 0; t <= MAX_TUPLE; t++) {
choose_table[s][t] = curr;
curr = curr * (s - t) % MOD * mod_inv(t + 1) % MOD;
}
}
int test_num;
std::cin >> test_num;
for (int t = 0; t < test_num; t++) {
int size;
int tuple_size;
int max_diff;
std::cin >> size >> tuple_size >> max_diff;
vector<int> arr(size);
for (int& i : arr) {
std::cin >> i;
}
std::sort(arr.begin(), arr.end());
long long valid_tuples = 0;
for (int i = 0; i < size; i++) {
int largest = std::upper_bound(arr.begin(), arr.end(), arr[i] + max_diff)
- arr.begin() - 1;
int valid_elements = largest - i;
valid_tuples = (valid_tuples + choose_table[valid_elements][tuple_size - 1]) % MOD;
}
cout << valid_tuples << '\n';
}
}
I first precalculate all the values of \binom{N}{M}, and then I used a binary search to see the largest value given the minimum value.
For some reason though, this TLEs, even though it should(?) meet the target complexity.