Problème A : Somme de Produits Triangulaires

Description : Étant donné trois entiers positifs \(A\), \(B\) et \(C\), calculer la valeur modulo \(998244353\) de la somme triple \(\sum_{a=1}^{A} \sum_{b=1}^{B} \sum_{c=1}^{C} a \times b \times c\).

Solution : La somme se factorise en \(\left( \sum_{a=1}^{A} a \right) \times \left( \sum_{b=1}^{B} b \right) \times \left( \sum_{c=1}^{C} c \right)\). Chaque somme arithmétique est calculée modulo \(998244353\) via la formule \(\frac{n(n+1)}{2}\).

#include <iostream>
using namespace std;

const long long MOD = 998244353;

long long sommeTriangle(long long n) {
    n %= MOD;
    return n * (n + 1) / 2 % MOD;
}

int main() {
    long long p, q, r;
    cin >> p >> q >> r;
    long long sp = sommeTriangle(p);
    long long sq = sommeTriangle(q);
    long long sr = sommeTriangle(r);
    long long res = sp * sq % MOD * sr % MOD;
    cout << res << endl;
    return 0;
}

Problème B : Comptage de Quadruplets

Description : Étant donné \(N\) et \(K\), compter les quadruplets \((a,b,c,d)\) avec \(1 \leq a,b,c,d \leq N\) tels que \(a + b - c - d = K\).

Solution : Décomposer en \(x = a + b\) et \(y = c + d\), avec \(x - y = K\). Pour chaque \(x\), le nombre de paires \((a,b)\) avec somme \(x\) est \(\min(x-1, 2N+1-x)\), et similaire pour \(y\). On itère sur \(x\) et agrège les contributions.

#include <iostream>
#include <algorithm>
using namespace std;

long long combinaisons(long long n, long long s) {
    if (s < 2 || s > 2 * n) return 0;
    return min(s - 1, 2 * n + 1 - s);
}

int main() {
    long long n, k;
    cin >> n >> k;
    long long total = 0;
    for (long long i = 2; i <= 2 * n; ++i) {
        total += combinaisons(n, i) * combinaisons(n, i - k);
    }
    cout << total << endl;
    return 0;
}

Problème C : Permutations par Échanges de Lignes et Colonnes

Description : Étant donné une matrice \(N \times N\) contenant les entiers de \(1\) à \(N^2\) et un entier \(K\), déterminer le nombre de matrices accessibles par échanges de lignes ou colonnes sous la contrainte que la somme des éléments concernés ne dépasse pas \(K\).

Solution : Modéliser les lignes et colonnes comme des graphes où une arête existe si l'échange est permis. Les composantes connexes permettent des permutaitons arbitraires. On utilise une structure union-find pour compter les tailles des composantes, puis le nombre de permutations est le produit des factorielles des tailles modulo \(998244353\).

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

const int MOD = 998244353;

vector<int> parentR, parentC;

int chercher(int x, vector<int>& parent) {
    if (parent[x] != x) parent[x] = chercher(parent[x], parent);
    return parent[x];
}

void unir(int x, int y, vector<int>& parent) {
    int rx = chercher(x, parent);
    int ry = chercher(y, parent);
    if (rx != ry) parent[rx] = ry;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> mat(n, vector<int>(n));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> mat[i][j];

    parentR.resize(n);
    parentC.resize(n);
    for (int i = 0; i < n; ++i) {
        parentR[i] = i;
        parentC[i] = i;
    }

    // Échanges de lignes possibles
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            bool ok = true;
            for (int l = 0; l < n; ++l) {
                if (mat[i][l] + mat[j][l] > k) {
                    ok = false;
                    break;
                }
            }
            if (ok) unir(i, j, parentR);
        }
    }

    // Échanges de colonnes possibles
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            bool ok = true;
            for (int l = 0; l < n; ++l) {
                if (mat[l][i] + mat[l][j] > k) {
                    ok = false;
                    break;
                }
            }
            if (ok) unir(i, j, parentC);
        }
    }

    // Tailles des composantes
    vector<int> tailR(n, 0), tailC(n, 0);
    for (int i = 0; i < n; ++i) {
        tailR[chercher(i, parentR)]++;
        tailC[chercher(i, parentC)]++;
    }

    // Calcul des permutations
    long long factLignes = 1, factColonnes = 1;
    for (int i = 0; i < n; ++i) {
        if (tailR[i] > 1) {
            long long f = 1;
            for (int j = 2; j <= tailR[i]; ++j) f = f * j % MOD;
            factLignes = factLignes * f % MOD;
        }
        if (tailC[i] > 1) {
            long long f = 1;
            for (int j = 2; j <= tailC[i]; ++j) f = f * j % MOD;
            factColonnes = factColonnes * f % MOD;
        }
    }

    cout << factLignes * factColonnes % MOD << endl;
    return 0;
}

Problème D : Dénombrement de Multimodèles

Description : Compter les multimodèles de taille \(N\) dont la somme est \(K\), avec des éléments de la forme \(\frac{1}{2^i}\) pour \(i \geq 0\).

Solution : Programmation dynamique. Soit \(dp[i][j]\) le nombre de multimodèles de taille \(i\) et somme \(j\). La récurrence est \(dp[i][j] = dp[i-1][j-1] + dp[i][2j]\) (si \(2j \leq K\)), avec \(dp[0][0]=1\).

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

const int MOD = 998244353;

int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 0));
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j > 0; --j) {
            dp[i][j] = dp[i-1][j-1];
            if (j * 2 <= k) {
                dp[i][j] = (dp[i][j] + dp[i][j * 2]) % MOD;
            }
        }
    }
    cout << dp[n][k] << endl;
    return 0;
}

Problème E : Matrice Mex

Description : Construire une matrice \(N \times N\) où les éléments de la première ligne et colonne sont donnés, et \(a_{i,j} = \text{mex}(a_{i-1,j}, a_{i,j-1})\) pour \(i,j \geq 2\). Le mex est le plus petit entier non négatif absent. Compter les occurrences de 0, 1 et 2.

Solution : Pour \(n\) petit, calculer directement la matrice. En observant des patterns, pour \(n \geq 5\), la matrice périodise, mais ici on remplit complètement pour compter.

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

int mex(int a, int b) {
    if (a != 0 && b != 0) return 0;
    if (a != 1 && b != 1) return 1;
    return 2;
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> grid(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == 0 || j == 0) {
                cin >> grid[i][j];
            }
        }
    }
    for (int i = 1; i < n; ++i) {
        for (int j = 1; j < n; ++j) {
            grid[i][j] = mex(grid[i-1][j], grid[i][j-1]);
        }
    }
    vector<int> compteur(3, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            compteur[grid[i][j]]++;
        }
    }
    for (int c : compteur) {
        cout << c << " ";
    }
    cout << endl;
    return 0;
}

Problème F : Maximisation du Profit avec Suppression de Sommets

Description : Étant donné un graphe avec \(N\) sommets et \(M\) arêtes, chaque sommet \(i\) a un coût de suppresison \(A_i\) et une valeur \(B_i\). Supprimer des sommets pour maximiser la somme des valeurs absolues des composantes connexes restantes moins le coût total.

Solution : Modélisation par flot réseau. Construire un graphe source-puits avec des arêtes représentant les choix de signe et les contraintes de connexité. La valeur absolue est gérée par des arêtes bidirectionnelles. Le profit maximum est la somme des \(|B_i|\) moins la coupe minimum.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

struct Edge {
    int to, capacity, next;
};

vector<Edge> edges;
vector<int> head;
int edgeCount = 0;

void addEdge(int from, int to, int cap) {
    edges.push_back({to, cap, head[from]});
    head[from] = edgeCount++;
    edges.push_back({from, 0, head[to]});
    head[to] = edgeCount++;
}

bool bfs(vector<int>& dist, int source, int sink) {
    fill(dist.begin(), dist.end(), INT_MAX);
    dist[source] = 0;
    queue<int> q;
    q.push(source);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i != -1; i = edges[i].next) {
            int v = edges[i].to;
            if (edges[i].capacity > 0 && dist[v] == INT_MAX) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist[sink] != INT_MAX;
}

int dfs(int u, int flow, int sink, vector<int>& dist) {
    if (u == sink) return flow;
    for (int i = head[u]; i != -1; i = edges[i].next) {
        int v = edges[i].to;
        if (edges[i].capacity > 0 && dist[v] == dist[u] + 1) {
            int pushed = dfs(v, min(flow, edges[i].capacity), sink, dist);
            if (pushed > 0) {
                edges[i].capacity -= pushed;
                edges[i ^ 1].capacity += pushed;
                return pushed;
            }
        }
    }
    return 0;
}

int dinic(int source, int sink, int nodes) {
    int totalFlow = 0;
    vector<int> dist(nodes);
    while (bfs(dist, source, sink)) {
        while (int flow = dfs(source, INT_MAX, sink, dist)) {
            totalFlow += flow;
        }
    }
    return totalFlow;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<long long> a(n), b(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    long long sumAbs = 0;
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
        sumAbs += abs(b[i]);
    }
    int totalNodes = 2 * n + 2;
    head.resize(totalNodes, -1);
    int source = 0, sink = 2 * n + 1;
    for (int i = 0; i < n; ++i) {
        addEdge(i, i + n, a[i] + abs(b[i]));
        if (b[i] >= 0) {
            addEdge(source, i, 2 * b[i]);
        } else {
            addEdge(i + n, sink, -2 * b[i]);
        }
    }
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        addEdge(u + n, v, INT_MAX);
        addEdge(v + n, u, INT_MAX);
    }
    long long minCut = dinic(source, sink, totalNodes);
    long long profit = sumAbs - minCut;
    cout << profit << endl;
    return 0;
}