Closed Tuples

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.

This implementation uses an insane amount of memory, but it still passes :smiley:.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using vl = vector<ll>;

const ll MOD = 1e9+7;
const ll MAX_N = 2e5 + 1;

ll C[MAX_N][101];

void findChooses(){
    for(int i=0; i<=MAX_N-1; i++){
        for(int j=0; j<=min(i, 100); j++){
            if(j == 0 || j == i){
                C[i][j] = 1;
            } else {
                C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
            }
        }
    }
}

ll choose(int n, int r){
    return C[n][r] % MOD;
}

void solve(int tc){
    int n, m, k; cin >> n >> m >> k;
    vl a(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    ll ans = 0;
    for(int i=0; i<n; i++){
        int tuples = upper_bound(a.begin(), a.end(), a[i] + k) - a.begin() - i;
        if(tuples >= m){
            ans += choose(tuples-1, m-1) % MOD;
        }
    }
    cout << ans % MOD << endl;
}

int main(){
    findChooses();
    int t; cin >> t;
    for(int i=1; i<=t; i++){
        solve(i);
    }
}

cin.tie(0)->sync_with_stdio(0)

Did you test it with that?

(also i fixed it, it just took precalculating the inverses)

no

lmao

lol, i just tested it

TLE on test case 1

The long long multiplication and inverse mod is probably at least 20x slower than Pascal’s triangle like in @jessechoe10 's solution.

Yeah, but my solution uses too much memory xD.