Máxima Suma de Prefijo

Si se establece una posición como la máxima suma de prefijo, entonces debe ser la máxima prefijo para el intervalo [1, pos], y los prefijos para [pos+1, n] deben ser menores o iguales a cero. Dado que n es pequeño (n ≤ 20), se puede aplicar programación dinámica con máscaras de bits. Definimos sum[S] como la suma de los elementos seleccionados en el estado S, f[S] como el número de formas para la primera mitad de la secuencia, y g[S] para la segunda mitad. La transición se detalla en el código siguiente.

#include <iostream>
#include <vector>
using namespace std;
const long long MOD = 1000000007;

void addModular(long long &a, long long b) {
    a = (a + b) % MOD;
}

int main() {
    int n;
    cin >> n;
    vector<int> values(n);
    for (int i = 0; i < n; i++) {
        cin >> values[i];
    }

    int total_states = 1 << n;
    vector<long long> sum_states(total_states, 0);
    vector<long long> ways_first(total_states, 0);
    vector<long long> ways_second(total_states, 0);

    for (int i = 0; i < n; i++) {
        ways_first[1 << i] = 1;
    }
    ways_second[0] = 1;

    for (int state = 0; state < total_states; state++) {
        for (int bit = 0; bit < n; bit++) {
            if (state & (1 << bit)) {
                sum_states[state] += values[bit];
            }
        }
    }

    for (int state = 0; state < total_states; state++) {
        if (sum_states[state] >= 0) {
            for (int bit = 0; bit < n; bit++) {
                if (!(state & (1 << bit))) {
                    addModular(ways_first[state | (1 << bit)], ways_first[state]);
                }
            }
        } else {
            for (int bit = 0; bit < n; bit++) {
                if (state & (1 << bit)) {
                    addModular(ways_second[state], ways_second[state ^ (1 << bit)]);
                }
            }
        }
    }

    long long result = 0;
    for (int state = 0; state < total_states; state++) {
        long long contrib = sum_states[state] * ways_first[state] % MOD * ways_second[(total_states - 1) ^ state] % MOD;
        addModular(result, contrib);
    }
    cout << result << endl;

    return 0;
}

Ranking Real

Para determinar el ranking real, consideramos dos casos: si la puntuación de una persona es fija o si cambia. Si es fija, los elementos que pueden cambiar son aquellos que ya son más altos y los que, después del cambio, siguen siendo más bajos. Si la puntuación cambia, los elementos con valores en [x, 2x) deben doblarse obligatoriamente. Al ordenar los puntajes y usar punteros dobles, se puede resolver en O(n log n). El código siguiente implementa esta lógica con combinatoria modular.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const long long MOD = 1000000007;

long long binom(int n, int k); // Función combinatoria precomputada

int main() {
    int n, k;
    cin >> n >> k;
    vector<pair<int, int>> scores(n);
    for (int i = 0; i < n; i++) {
        cin >> scores[i].first;
        scores[i].second = i;
    }

    sort(scores.begin(), scores.end(), greater<pair<int, int>>());

    vector<int> boundary(n);
    int last = 0;
    for (int i = 1; i < n; i++) {
        if (scores[i].first != scores[i-1].first) {
            for (int j = last; j < i; j++) {
                boundary[j] = i - 1;
            }
            last = i;
        }
    }
    for (int j = last; j < n; j++) {
        boundary[j] = n - 1;
    }

    vector<int> next_ptr(n), prev_ptr(n);
    int left = n - 1;
    for (int i = n - 1; i >= 0; i--) {
        while (left >= 0 && scores[i].first > scores[left].first * 2) {
            left--;
        }
        next_ptr[i] = left + 1;
    }

    int right = 0;
    for (int i = 0; i < n; i++) {
        while (right < n && scores[i].first * 2 <= scores[right].first) {
            right++;
        }
        prev_ptr[i] = right - 1;
    }

    vector<long long> results(n);
    for (int i = 0; i < n; i++) {
        if (i > 0 && scores[i].first == scores[i-1].first) {
            results[scores[i].second] = results[scores[i-1].second];
        } else if (scores[i].first == 0) {
            results[scores[i].second] = binom(n, k);
        } else {
            int equal_count = boundary[i] - i;
            int not_doubled = i - prev_ptr[i];
            int must_double = next_ptr[i] - i;
            long long part1 = binom(n - must_double + equal_count, k);
            long long part2 = binom(n - not_doubled - equal_count, k - not_doubled - equal_count);
            results[scores[i].second] = (part1 + part2) % MOD;
        }
    }

    for (int i = 0; i < n; i++) {
        cout << results[i] << endl;
    }

    return 0;
}

Juego Divino

Para el juego divino, si existe un borde de longitud x, entonces n-x es un período válido. Si para algún i y j con i ≡ j mod (n-x), los caracteres s[i] y s[j] son 0 y 1 respectivamente, entonces x no es un borde válido. Se puede usar la transformada rápida de Fourier para optimizar la verificación de bordes. El código siguiente calcula la convolución de polinomios para detectar conflictos.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

vector<int> polynomial_multiply(const vector<int>& a, const vector<int>& b); // FFT implementation

int main() {
    char str[100000];
    scanf("%s", str);
    int len = strlen(str);

    vector<int> poly0(len, 0), poly1(len, 0);
    for (int i = 0; i < len; i++) {
        poly0[i] = (str[i] == '0');
        poly1[i] = (str[len - 1 - i] == '1');
    }

    vector<int> conv = polynomial_multiply(poly0, poly1);

    long long answer = 1LL * len * len;
    for (int period = 1; period < len; period++) {
        bool valid = true;
        for (int j = period; j < len; j += period) {
            if (conv[len - 1 + j] + conv[len - 1 - j] > 0) {
                valid = false;
                break;
            }
        }
        if (valid) {
            answer ^= (1LL * (len - period) * (len - period));
        }
    }

    printf("%lld\n", answer);
    return 0;
}

Viaje Interestelar

Para calcular el promedio de distancias en el viaje interestelar, se puede precomputar usando subida binaria. Definimos f[i][j] como el punto izquierdo alcanzable desde i con 2^j pasos, y g[i][j] como la suma de distancias desde i hasta f[i][j]. Las recurrencias se basan en propiedades de mínimos y acumulación de distancias. El siguiente código inicializa estas estructuras y calcula distancias para consultas.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

void initialize(int n, const vector<int>& left_bound, vector<vector<int>>& f, vector<vector<long long>>& g) {
    int max_log = log2(n) + 1;
    vector<int> pow2(max_log + 1);
    pow2[0] = 1;
    for (int i = 1; i <= max_log; i++) {
        pow2[i] = pow2[i-1] * 2;
    }

    f.assign(n+1, vector<int>(max_log+1, 0));
    g.assign(n+1, vector<long long>(max_log+1, 0));

    f[n][0] = left_bound[n];
    for (int i = n-1; i >= 1; i--) {
        f[i][0] = min(f[i+1][0], left_bound[i]);
        g[i][0] = i - f[i][0];
    }

    for (int j = 1; j <= max_log; j++) {
        for (int i = 1; i <= n; i++) {
            if (f[i][j-1] > 0) {
                f[i][j] = f[f[i][j-1]][j-1];
                g[i][j] = g[i][j-1] + g[f[i][j-1]][j-1] + (f[i][j-1] - f[i][j]) * pow2[j-1];
            }
        }
    }
}

long long calculate_distance(int x, int left_limit, const vector<int>& left_bound, const vector<vector<int>>& f, const vector<vector<long long>>& g, int max_log) {
    if (left_bound[x] <= left_limit) {
        return x - left_limit;
    }
    long long distance = x - left_bound[x];
    int current = left_bound[x];
    int steps = 1;
    for (int j = max_log; j >= 0; j--) {
        if (f[current][j] >= left_limit) {
            distance += g[current][j] + steps * (current - f[current][j]);
            steps += (1 << j);
            current = f[current][j];
        }
    }
    if (current > left_limit) {
        distance += current - left_limit + steps * (current - left_limit);
    }
    return distance;
}