La clé de ce problème réside dans la notion d'« inclusion stricte ». Initialement, j'ai négligé cet aspect et j'ai eu du mal à trouver une solution.

Dans le cas d'une inclusion stricte, nous devons sélectionner 2k arêtes respectivement horizontalement et verticalement. Les directions horizontale et verticale étant indépendantes, nous pouvons appliquer le principe de multiplication et nous concentrer sur une seule direction.

#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 100000
#define Mod 1000000007
#define LL long long

using namespace std;

int n,m,k;
LL facteur[maxn];

int lecture(){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
    return s*w;
}

void initialisation(){
    facteur[0]=1;
    for(int i=1;i<=10000;i++)
        facteur[i]=facteur[i-1]*i%Mod;
}

LL puissance_rapide(LL x,LL y){
    LL res=1;
    while(y){
        if(y&1) res=res*x%Mod;
        x=x*x%Mod;y>>=1; 
    }
    return res; 
} 

LL combinaison(LL N,LL M){
    if(N<M) return 0;
    return facteur[N]*puissance_rapide(facteur[M]*facteur[N-M]%Mod,Mod-2)%Mod; 
}

signed main(){
    initialisation();
    n=lecture();m=lecture();k=lecture();
    cout<<1ll*combinaison(n-1,2*k)*combinaison(m-1,2*k)%Mod; 
    return 0;
}

CF111D Petya et Coloriage

Après réflexion, si nous considérons une seule couleur, elle doit apparaître dans toutes les colones de 1 à n.

Pour plusieurs couleurs, chaque couleur ne doit ni ne peut remplir entièrement une ligne ou une colonne consécutive. Il suffit qu'il y ait une intersection entre les lignes 1 et 2, ainsi qu'entre les lignes n et n-1.

Par conséquent, nous devonns traiter les deux côtés. Soit f[i][j] le nombre de façons de colorier les i premières cases avec j couleurs. Nous traitons séparément le nombre de couleurs sur les côtés f[n][i] et les j couleurs pour la partie centrale j^(n(m-2)). Cette dernière formule n'était pas immédiatement évidente, mais en réfléchissant, n lignes et m-2 colones semblent raisonnables (en exculant les deux colones des extrémités).

Il faut ensuite multiplier par les permutations de toutes les couleurs et le nombre de combinaisons pour choisir k couleurs.

#include<bits/stdc++.h>
#define LL long long
#define Mod 1000000007
#define maxn 1000010

using namespace std;

int n,m,k,reponse;
int f[1010][1010],facteur[maxn],inv[maxn];

int lecture(){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
    return s*w;
}

LL puissance_rapide(LL x,LL y){
    LL resultat=1;
    while(y){
        if(y&1)resultat=resultat*x%Mod;
        x=x*x%Mod;y>>=1;
    }
    return resultat;
}

LL C(int x,int y){
    if(y>x)return 0;
    return facteur[x]*inv[y]%Mod*inv[x-y]%Mod; 
}

LL car(LL x){
    return x*x%Mod;
}

void initialisation(){
    f[0][0]=1;
    facteur[0]=inv[0]=facteur[1]=inv[1]=1;
    for(int i=2;i<=1000000;i++){
        facteur[i]=(facteur[i-1]*i)%Mod;
        inv[i]=(Mod-Mod/i)*inv[Mod%i]%Mod;
    }
    for(int i=1;i<=1000000;i++)inv[i]=inv[i]*inv[i-1]%Mod;
}

int main(){
    initialisation();
    n=lecture();m=lecture();k=lecture();
    
    if(m==1){
        cout<<puissance_rapide(k,n);
        return 0;
    }
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i&&j<=k;j++)
            f[i][j]=(f[i-1][j-1]+f[i-1][j]*j)%Mod;
    for(int i=0;i<=n;i++){
        LL temp=puissance_rapide(i,n*(m-2))*C(k,i)%Mod;
        for(int j=i;j<=n;j++)
            reponse=(reponse+temp*C(k-i,(j-i)*2)%Mod*C((j-i)*2,j-i)%Mod*car(f[n][j]*facteur[j]%Mod)%Mod)%Mod;
    }
    cout<<(reponse%Mod+Mod)%Mod;
    return 0;
}

CF886E Élément Maximum

Soit f[i] le nombre de solutions valides jusqu'au i-ème élément sans erreur.

La relation de récurrence est : f[i] = somme de j=i-k+1 à i de C[i-1][i-j] × (i-j)! × f[j-1]

Pour obtenir la réponse, nous appliquons cette méthode à chaque position, calculons toutes les solutions valides, puis soustrayons les solutions invalides.

L'implémentation peut être optimisée en utilisant g[i] = f[i]/i! ce qui simplifei les calculs.