A. Génération de Chaînes Binaires (P6191)

On commence par compter les solutions avec 0 ou 1 seul '1'. Ensuite, on modélise la séquence comme une succession de blocs "1 suivi de k zéros", terminée par un '1'. Pour i occurrences de '1', la longueur minimale est j = (k + 1)(i - 1) + 1. Si j dépasse n, on arrête. Sinon, on calcule le nombre de combinaisons :

\[C(n - j + i, i)\] Cela revient à insérer i '1' dans les positions disponibles, en traitant les zéros comme indistincts après suppression des blocs structurants.

#include<iostream>
using namespace std;
const int MOD = 5000011;

long long puissance_mod(long long base, long long exp) {
    long long res = 1;
    while (exp) {
        if (exp & 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return res;
}

long long coefficient_binomial(long long n, long long k) {
    if (k < 0 || k > n) return 0;
    long long num = 1, denom = 1;
    for (int i = 1; i <= k; i++) {
        num = num * (n - i + 1) % MOD;
        denom = denom * i % MOD;
    }
    return num * puissance_mod(denom, MOD - 2) % MOD;
}

int main() {
    int n, k;
    cin >> n >> k;
    long long res = 1 + n;
    for (int i = 2; i <= n; i++) {
        int longueur_min = (k + 1) * (i - 1) + 1;
        if (longueur_min > n) break;
        res = (res + coefficient_binomial(n - longueur_min + i, i)) % MOD;
    }
    cout << res;
}

B. Ratio de Séquence Binaire (P1641)

Le problème se résout par une formule combinatoire dérivée de l'analyse des chemins de Dyck. Le résultat est donné par :

\[\frac{n - m + 1}{n + 1}\] On évite les erreurs de précision en simplifiant algébriquement avant l'évaluation numérique.

#include<cstdio>
int main() {
    int T, taureaux, vaches;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &taureaux, &vaches);
        if (vaches > taureaux) printf("0.000000\n");
        else printf("%.6f\n", (taureaux - vaches + 1.0) / (taureaux + 1));
    }
}

C. Arrangement de Troupeau avec Contraintes (P3223)

On utilise une approche par complémentarité. Le nombre total d'arrangements sans restrictions est :

\[(n+2)! \timess m! \times \binom{n+3}{m}\] On soustrati les configurations où deux entités spécifiques sont adjacentes, équivalentes à :

\[2! \times (n+1)! \times m! \times \binom{n+2}{m}\] La différence donne le résultat final. Une implémentation nécessite une arithmétique en précision arbitraire.

D. Configuration de Troupeau avec Déséquilibre Limité (P2592)

On utilise une DP à quatre dimensions : dp[a][b][c][d] représente le nombre de configurations avec a taureaux, b vaches, un excès maximal de taureaux c, et un excès maximal de vaches d. Les transitions mettent à jour les déséquilibres lors de l'ajout d'un taureau ou d'une vache.

#include<cstdio>
const int MOD = 12345678;
int dp[155][155][25][25];

int main() {
    int taureaux, vaches, max_diff;
    scanf("%d%d%d", &taureaux, &vaches, &max_diff);
    dp[0][0][0][0] = 1;
    for (int a = 0; a <= taureaux; a++) {
        for (int b = 0; b <= vaches; b++) {
            for (int exc_t = 0; exc_t <= max_diff; exc_t++) {
                for (int exc_v = 0; exc_v <= max_diff; exc_v++) {
                    if (!dp[a][b][exc_t][exc_v]) continue;
                    int val = dp[a][b][exc_t][exc_v];
                    if (a < taureaux && exc_t < max_diff) {
                        int new_exc_v = (exc_v > 0) ? exc_v - 1 : 0;
                        dp[a+1][b][exc_t+1][new_exc_v] = (dp[a+1][b][exc_t+1][new_exc_v] + val) % MOD;
                    }
                    if (b < vaches && exc_v < max_diff) {
                        int new_exc_t = (exc_t > 0) ? exc_t - 1 : 0;
                        dp[a][b+1][new_exc_t][exc_v+1] = (dp[a][b+1][new_exc_t][exc_v+1] + val) % MOD;
                    }
                }
            }
        }
    }
    int total = 0;
    for (int exc_t = 0; exc_t <= max_diff; exc_t++) {
        for (int exc_v = 0; exc_v <= max_diff; exc_v++) {
            total = (total + dp[taureaux][vaches][exc_t][exc_v]) % MOD;
        }
    }
    printf("%d", total);
}