Problème 1 : Sommes de Sous-ensembles (Collection)

L'objectif est de calculer le produit de toutes les sommes possibles de sous-ensembles, chacune élevée à la puissance de sa fréquence d'apparition. Le cœur du problème repose sur un sac à dos (knapsack) pour compter ces occurrences.

Soit $f[j]$ le nombre de façons d'obtenir une somme $j$. En raison du Petit Théorème de Fermat, lors du calcul du produit modulaire $ans = \prod j^{f[j]} \pmod M$, l'exposant $f[j]$ doit être calculé modulo $(M-1)$.

#include <iostream>
#include <vector>

using namespace std;

const int MODULO = 998244353;
const int PHI_MOD = MODULO - 1;

long long rapide_exp(long long base, int exp) {
    long long res = 1;
    base %= MODULO;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MODULO;
        base = (base * base) % MODULO;
        exp /= 2;
    }
    return res;
}

int main() {
    int n;
    if (!(cin >> n)) return 0;

    int max_sum = n * (n + 1) / 2;
    vector<int> dp_frequence(max_sum + 1, 0);
    dp_frequence[0] = 1;

    for (int i = 1; i <= n; ++i) {
        for (int j = (i * (i + 1) / 2); j >= i; --j) {
            dp_frequence[j] = (dp_frequence[j] + dp_frequence[j - i]) % PHI_MOD;
        }
    }

    long long resultat_final = 1;
    for (int j = 1; j <= max_sum; ++j) {
        if (dp_frequence[j] > 0) {
            resultat_final = (resultat_final * rapide_exp(j, dp_frequence[j])) % MODULO;
        }
    }

    cout << resultat_final << endl;
    return 0;
}

Problème 2 : Gestion de Placement et Segment Tree (Lantern)

Le problème revient à vérifier si une configuration de placement respecte certaines contraintes de densité. Mathématiquement, la condition de validité est équivalente à vérifier que la somme maximale d'un suffixe (basée sur l'écart entre les demandes et la capacité $k$) ne dépasse pas un seuil $d \cdot k$.

On utilise un arbre de segments pour maintenir la "somme maximale de sous-segment" de manière dynamique, permettant des mises à jour ponctuellse et des requêtes globales en $O(\log n)$.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct SegmentNode {
    long long total_sum;
    long long max_prefix;
    long long max_suffix;
    long long max_sub;
};

int N_size, M_queries, D_dist;
long long K_cap;
vector<SegmentNode> tree;

void update_node(int p) {
    tree[p].total_sum = tree[2 * p].total_sum + tree[2 * p + 1].total_sum;
    tree[p].max_prefix = max(tree[2 * p].max_prefix, tree[2 * p].total_sum + tree[2 * p + 1].max_prefix);
    tree[p].max_suffix = max(tree[2 * p + 1].max_suffix, tree[2 * p + 1].total_sum + tree[2 * p].max_suffix);
    tree[p].max_sub = max({tree[2 * p].max_sub, tree[2 * p + 1].max_sub, tree[2 * p].max_suffix + tree[2 * p + 1].max_prefix});
}

void build_tree(int l, int r, int p) {
    if (l == r) {
        tree[p] = {-K_cap, 0, 0, 0};
        return;
    }
    int mid = (l + r) / 2;
    build_tree(l, mid, 2 * p);
    build_tree(mid + 1, r, 2 * p + 1);
    update_node(p);
}

void modify(int l, int r, int p, int idx, int val) {
    if (l == r) {
        tree[p].total_sum += val;
        long long v = max(0LL, tree[p].total_sum);
        tree[p].max_prefix = tree[p].max_suffix = tree[p].max_sub = v;
        return;
    }
    int mid = (l + r) / 2;
    if (idx <= mid) modify(l, mid, 2 * p, idx, val);
    else modify(mid + 1, r, 2 * p + 1, idx, val);
    update_node(p);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N_size >> M_queries >> K_cap >> D_dist;
    tree.resize(4 * N_size + 1);
    build_tree(1, N_size, 1);

    while (M_queries--) {
        int pos, val;
        cin >> pos >> val;
        modify(1, N_size, 1, pos, val);
        cout << (tree[1].max_sub <= (long long)D_dist * K_cap ? "YES" : "NO") << "\n";
    }
    return 0;
}

Problème 3 : DP sur Arbre et Contraintes (Connection)

On cherche à trouver la composante connexe de valeur maximale dans un arbre, sous réserve de certaines contraintes d'exclusion entre nœuds. Soit $f[i][j]$ la valeur maximale d'une composante enracinée en $i$ dont le dernier nœud dans l'ordre DFS est $j$.

L'optimisation consiste à remarquer que le nombre de nœuds impliqués dans des contraintes explicites est faible ($2m$). On peut donc remapper ces nœuds pour réduire la complexité de la DP à $O(nm)$, où $m$ est le nombre de contraintes.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const long long INF = 1e16;
int n, m, mapped_id[100005], id_counter;
long long weights[100005], dp[100005][45], global_max;
bool conflict[45][45];
vector<int> adj[100005];

void solve_tree(int u, int p) {
    dp[u][mapped_id[u]] = weights[u];
    for (int v : adj[u]) {
        if (v == p) continue;
        solve_tree(v, u);
        for (int j = 0; j <= id_counter; ++j) {
            long long best_prev = -INF;
            for (int k = 0; k <= id_counter; ++k) {
                if (!conflict[k][mapped_id[v]]) best_prev = max(best_prev, dp[u][k]);
            }
            dp[u][j] = max(dp[u][j], best_prev + dp[v][j]);
        }
    }
    for (int j = 0; j <= id_counter; ++j) global_max = max(global_max, dp[u][j]);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> weights[i];
    for (int i = 1; i <= n; ++i) {
        int count; cin >> count;
        while (count--) { int neighbor; cin >> neighbor; adj[i].push_back(neighbor); }
    }
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        if (!mapped_id[u]) mapped_id[u] = ++id_counter;
        if (!mapped_id[v]) mapped_id[v] = ++id_counter;
        conflict[mapped_id[u]][mapped_id[v]] = conflict[mapped_id[v]][mapped_id[u]] = true;
    }
    for (int i = 0; i <= n; ++i) for (int j = 0; j < 45; ++j) dp[i][j] = -INF;
    solve_tree(1, 0);
    cout << global_max << endl;
    return 0;
}

Problème 4 : Combinatoire et État de Jeu (Checkers)

Le nombre de configurations valides pour une séquence de pions peut être modélisé par une formule combinatoire $\binom{n-a-b}{a}$, où $a$ est le nombre de paires de pions consécutifs et $b$ le nombre de pions isolés.

Pour gérer les points d'interrogation ('?'), on utilise une DP pour compter le nombre de façons d'obtenir chaque paire $(a, b)$. L'état de la DP inclut la position actuelle, les compteurs $a$ et $b$, et l'état du dernier pion placé (0: vide, 1: pion isolé, 2: partie d'une paire).

#include <iostream>
#include <vector>
#include <string>

using namespace std;

const int MOD = 1e9 + 7;
long long memo[2][255][255][3];
long long fact[505], invFact[505];

long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

long long nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}

int main() {
    int n; cin >> n;
    string s; cin >> s;
    s = " " + s;

    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = (fact[i - 1] * i) % MOD;
    invFact[n] = power(fact[n], MOD - 2);
    for (int i = n - 1; i >= 0; i--) invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;

    memo[0][0][0][0] = 1;
    for (int i = 1; i <= n; i++) {
        int cur = i & 1, prev = (i - 1) & 1;
        for (int x = 0; x <= n / 2; x++) {
            for (int y = 0; y <= n; y++) {
                for (int k = 0; k < 3; k++) memo[cur][x][y][k] = 0;
                
                if (s[i] != '1') {
                    memo[cur][x][y][0] = (memo[prev][x][y][0] + memo[prev][x][y][1] + memo[prev][x][y][2]) % MOD;
                }
                if (s[i] != '0') {
                    if (y > 0) memo[cur][x][y][1] = (memo[prev][x][y - 1][0] + memo[prev][x][y - 1][2]) % MOD;
                    if (x > 0 && y < n) memo[cur][x][y][2] = memo[prev][x - 1][y + 1][1];
                }
            }
        }
    }

    long long total_ans = 0;
    for (int x = 0; x <= n / 2; x++) {
        for (int y = 0; y <= n; y++) {
            long long ways = (memo[n & 1][x][y][0] + memo[n & 1][x][y][1] + memo[n & 1][x][y][2]) % MOD;
            if (ways > 0) {
                total_ans = (total_ans + nCr(n - x - y, x) * ways) % MOD;
            }
        }
    }
    cout << total_ans << endl;
    return 0;
}