Lien de l'article : Construction de Matrice

Description du Problème

Nous devons construire une matrice entière n×m.

La matrice construite doit satisfaire :

Le produit de tous les éléments dans chaque ligne doit être égal à k.
Le produit de tous les éléments dans chaque colonne doit être égal à k.
Assurez-vous que k est soit 1 soit −1.

Veuillez calculer le nombre total de matrices différentes qui satisfont ces conditions.

Comme le résultat peut être très grand, vous n'avez qu'à retourner le résultat modulo 109+7.

Format d'entrée :
Une seule ligne contenant trois entiers n, m, k.

Format de sortie :
Un entier, représentant le résultat modulo 109+7.

Plages de données :
Les trois premiers points de test satisfont 1≤n,m≤3.
Tous les points de test satisfont 1≤n,m≤1018, k est soit 1 soit −1.


Difficulté : Difficile
Limites de temps/ESPACE : 1s / 256MB
Nombre total de passages réussis : 300
Nombre total d'essais : 1360
Source : AcWing, Semaine 127
Tags Algorithmiques

Exemples

Exemple d'entrée 1 :
1 1 -1
Exemple de sortie 1 :
1
Exemple d'entrée 2 :
1 3 1
Exemple de sortie 2 :
1
Exemple d'entrée 3 :
3 3 -1
Exemple de sortie 3 :
16

Algorithme 1

(Deux fois exponentaition rapide) \(O(log(n-1 * m-1))\)

Astuce :

Considérez la dernière ligne et la dernière colonne, concentrez-vous sur le rectangle n-1 * m-1 en haut à gauche. Chaque case de ce rectangle peut être soit 1 soit -1, ce qui donne 2^(n-1)(m-1) façons différentes. Pour chaque ligne, le dernier élément est déterminé par les précédents pour que le produit soit k. Pour chaque colonne, le dernier élément est déterminé par les précédents pour que le produit soit k. Cependant, le point en bas à droite peut ne pas être déterminé.

A B C représante la zone concernée par le produit.

Considérez la dernière ligne, le produit de chaque ligne doit être k, donc xA = k, donc x = k/A. Considérez la dernière colonne, le produit de chaque colonne doit être k, donc xB = k, donc x = k/B. Pour que x soit cohérent, il faut que k/A = k/B, c'est-à-dire A doit égaler B. A et B sont déterminés par le rectangle en haut à gauche. AC est le produit des m-1 colonnes, chaque colonne a pour produit k, donc AC = k^(m-1). BC est le produit des n-1 lignes, chaque ligne a pour produit k, donc BC = k^(n-1).

Ainsi, A = k^(m-1) / C, B = k^(n-1) / C. Pour que A = B, pour k=1, c'est toujours vrai. Pour k=-1, il faut que m-1 et n-1 aient la même parité, sinon ce n'est pas posible.

Dans le cas où cela est vrai, le nombre de façons est le nombre de configurations du rectangle en haut à gauche, c'est-à-dire 2^(n-1)(m-1). Comme l'exposant peut être très grand, on utilise l'exponentiation rapide. On peut aussi utiliser la fonction d'Euler car a^(p-1) ≡ 1 mod p pour a et p premiers.

Code C++ 1

#include<iostream>
using namespace std;
const int  mod=10e9+7;
typedef long long LL;

LL qmi(LL a,LL k,LL p)
{
    long long res=1;
    
    while(k)
    {
        if(k&1)
        {
            res=res*a%p;
        }
        k>>=1;
        a=a*a%p;
    }
    
    return res;
}
int main()
{
    long long n,m,k;
    cin>>n>>m>>k;
    
    if(n==1||m==1)
    {
        cout<<1<<endl;
        
        return 0;
    }
     LL p = qmi(2, n - 1, mod);
     if((n + m) & 1) cout << 0;
        else cout << qmi(p, m - 1, mod);
        
    return 0;
}

Algorithme 2

(Fonction d'Euler) \(O(log(n-1 * m-1))\)

Code C++ 2

#include<iostream>
using namespace std;
const int  mod=1e9+7;
typedef long long LL;

LL qmi(LL a,LL k,LL p)
{
    long long res=1;
    
    while(k)
    {
        if(k&1)
        {
            res=res*a%p;
        }
        k>>=1;
        a=a*a%p;
    }
    
    return res;
}
int main()
{
    LL n, m, k;
    cin >> n >> m >> k;

    if (k == -1 && n % 2 != m % 2) puts("0");
    else
    {
        LL t = (n - 1) % (mod - 1) * ((m - 1) % (mod - 1)) % (mod - 1);
        cout << qmi(2, t, mod) << endl;
    }

    return 0;
}