A. Preenchimento de Grade

Problema baseado em Luogu P3197 [HNOI2008] Prison Break.

Aqui está um método para conjecturar uma fórmula: do complexo para o simples, progredindo do superficial para o profundo, encontrando padrões através de força bruta.

Uma versão simplificada deste problema, com m fixo em 3, apareceu anteriormente em uma simulação. Para essa versão, uma busca exaustiva revelou que quando n é ímpar, a resposta é 2^n - 2, e quando n é par, é 2^n + 2, com um caso especial para n = 1. Notando a semelhança com o problema atual, onde m agora é variável, surgiu a ideia de conjecturar uma fórmula mais geral.

Propuseram-se expressões da forma (m - 1)^n ± (m - 1). Testando com valores pequenos para n e m, a hipótese parecia se confirmar.

Dada a aparente complexidade do problema em derivar uma solução formal, decidiu-se utilizar essa conjectura. A implementação baseada nessa ideia foi aceita.

Embora abordagem seja empírica, ela ilustra que, ao enfrentar um problema baseado em uma conclusão obscura, examinar casos menos complexos para identificar padrões pode ser uma estratégia viável. Não há garantia absoluta, mas possui um grau razoável de confiança.

Atenção: Em operações de subtração com módulo, é essencial adicionar o módulo ao resultado para evitar valores negativos. Ignorar isso resultou na perda de 20 pontos em uma aparente correção formal, um alerta importante.

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9 + 7;

int potencia_rapida(int base, int exp) {
    int resultado = 1;
    while (exp) {
        if (exp & 1) resultado = (resultado * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return resultado;
}

signed main() {
    int elementos, tipos;
    while (~scanf("%lld%lld", &elementos, &tipos)) {
        if (elementos == 1) {
            printf("%lld\n", tipos % MOD);
        } else if (elementos & 1) {
            printf("%lld\n", (potencia_rapida((tipos - 1), elementos) % MOD - tipos + 1 + MOD) % MOD);
        } else {
            printf("%lld\n", (potencia_rapida((tipos - 1), elementos) % MOD + (tipos - 1)) % MOD);
        }
    }
    return 0;
}

B. Subsequência Não Estritamante Crescente (syoj.1768)

Problema baseado em bzoj.4403.

O objetivo é contar o número de sequências de comprimento 1 a n, com elementos dentro do intervalo [A, B], que são não estritamente crescentes.

Considere criar B - A + 1 caixas, cada uma correspondendo a um valor no intervalo [A, B]. Os n elementos são então alocados nesssas caixas. Para garantir que sequências de todos os comprimentos possíveis de 1 a n sejam contadas, uma caixa adicional é introduzida para alocar os elementos "excedentes".

O problema é então transformado no clássico problema de distribuição de bolas em caixas, onde as bolas são indistinguíveis e as caixas são distintas, permitindo caixas vazias. O número de formas de distribuir as bolas corresponde ao número de sequências válidas. A fórmula resultante é C(B - A + 1 + n, B - A + 1) - 1. A subtração de 1 remove o caso onde todas as bolas são colocadas na caixa extra.

Como as caixas representam valores em ordem crescente, qualquer distribuição resulta em uma sequência não estritamente crescente. Para calcular a combinação módulo um número primo, utiliza-se o Teorema de Lucas.

Observação Importente: Ao calcular combinações C(n, k), é crucial verificar se n >= k. Em problemas onde o módulo é aplicado, os valores podem se tornar menores que o esperado, tornando essa verificação necessária. A omissão dessa verificação levou a um erro de solução.

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD_PRIMO = 1e6 + 3;
ll fatorial[MOD_PRIMO];
int testes;

void precomputar_fatoriais() {
    fatorial[0] = 1;
    for (int i = 1; i < MOD_PRIMO; i++) {
        fatorial[i] = (fatorial[i - 1] * i) % MOD_PRIMO;
    }
}

ll exponenciacao_modular(ll base, ll exp) {
    ll res = 1;
    base %= MOD_PRIMO;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD_PRIMO;
        base = (base * base) % MOD_PRIMO;
        exp /= 2;
    }
    return res;
}

ll combinacao_mod(ll n, ll k) {
    if (k < 0 || k > n) return 0;
    return fatorial[n] * exponenciacao_modular(fatorial[k], MOD_PRIMO - 2) % MOD_PRIMO *
           exponenciacao_modular(fatorial[n - k], MOD_PRIMO - 2) % MOD_PRIMO;
}

ll lucas(ll n, ll k) {
    if (k == 0) return 1;
    return (lucas(n / MOD_PRIMO, k / MOD_PRIMO) * combinacao_mod(n % MOD_PRIMO, k % MOD_PRIMO)) % MOD_PRIMO;
}

int main() {
    precomputar_fatoriais();
    scanf("%d", &testes);
    while (testes--) {
        ll n, lim_inf, lim_sup;
        scanf("%lld%lld%lld", &n, &lim_inf, &lim_sup);
        ll intervalo = lim_sup - lim_inf + 1;
        printf("%lld\n", (lucas(intervalo + n, intervalo) - 1 + MOD_PRIMO) % MOD_PRIMO);
    }
    return 0;
}

C. Festival de Blocos (syoj.1769)

Problema baseado em Luogu P4071 [SDOI2016] Arrangement Count.

Dada a descrição, o problema pede o número de permutações dos números 1 a n tal que exatamente m números permanecem em suas posições originais, enquanto os outros n - m números estão todos em posições diferentes das originais.

Isso é diretamente resolvido utilizando a fórmula dos números de permutação com restrições (Derangements). A solução consiste em escolher m posições para manter fixas (combinação C(n, m)), e então calcular o número de derangements para os n - m elementos restantes, denotado como D[n - m]. A resposta é C(n, m) * D[n - m].

Para calcular os números de derangement D[i]: seja D[i] o número de permutações de i elementos onde nenhum está em sua posição original. Claramente, D[0] = 1, D[1] = 0 e D[2] = 1. Para o elemento na primeira posição, existem i - 1 escolhas possíveis. Se o elemento j for colocado na posição i, o número de maneiras de arranjar o restante depende de onde o elemento i é colocado. Isso leva à relação de recorrência: D[i] = (i - 1) * (D[i - 1] + D[i - 2])

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MODULO = 1e9 + 7;
const int MAXIMO = 1e6 + 10;
int testes, n, m;
ll derangement[MAXIMO], fatorial[MAXIMO];

ll exponencia_modular_rapida(ll base, ll exp) {
    ll resultado = 1;
    base %= MODULO;
    while (exp > 0) {
        if (exp & 1) resultado = (resultado * base) % MODULO;
        base = (base * base) % MODULO;
        exp >>= 1;
    }
    return resultado;
}

ll combinatorio_mod(ll total, ll escolhidos) {
    if (escolhidos < 0 || escolhidos > total) return 0;
    return fatorial[total] * exponencia_modular_rapida(fatorial[escolhidos], MODULO - 2) % MODULO *
           exponencia_modular_rapida(fatorial[total - escolhidos], MODULO - 2) % MODULO;
}

void precomputar() {
    fatorial[0] = 1;
    derangement[0] = 1;
    derangement[1] = 0;
    if (MAXIMO > 2) derangement[2] = 1;
    for (int i = 3; i < MAXIMO; i++) {
        derangement[i] = ((i - 1LL) * (derangement[i - 1] + derangement[i - 2])) % MODULO;
    }
    for (int i = 1; i < MAXIMO; i++) {
        fatorial[i] = (fatorial[i - 1] * i) % MODULO;
    }
}

int main() {
    precomputar();
    scanf("%d", &testes);
    while (testes--) {
        scanf("%d%d", &n, &m);
        printf("%lld\n", combinatorio_mod(n, m) * derangement[n - m] % MODULO);
    }
    return 0;
}