L'énoncé du problème stipule que pour une matrice a[i][j], les conditions suivantes doivent être satisfaites : a[i][j] % a[i-1][j] == 0 && a[i][j] % a[i][j-1] == 0. Une solution possible utilise un parcours en profondeur d'abord (DFS).

#include<bits/stdc++.h>
using namespace std;
#define Pour(i,a,b) for(int i = a; i <= b; i++)
typedef long long ll;
const int mod = 1e9 + 7;
int valeurs[4] = {1,2,1009,2018};
int grille[2100][2100],taille_n,taille_m,solutions;

void explorer(int x,int y){
    if(x == taille_n + 1){
        solutions++;
    }else{
        if(x == 1){
            Pour(i,0,3){
                if(grille[x][y - 1] % valeurs[i] == 0 && !grille[x][y]){
                    grille[x][y] = valeurs[i];
                    if(y != taille_m) explorer(x,y + 1);
                    else explorer(x + 1,1);
                    grille[x][y] = 0;
                }
            }
        }else if(y == 1){
            Pour(i,0,3) {
                if (grille[x - 1][y] % valeurs[i] == 0 && !grille[x][y]){
                    grille[x][y] = valeurs[i];
                    if(y != taille_m) explorer(x,y + 1);
                    else explorer(x + 1,1);
                    grille[x][y] = 0;
                }
            }
        }else if(x <= taille_n && y <= taille_m){
            Pour(i,0,3){
                if(grille[x - 1][y] % valeurs[i] == 0 && grille[x][y - 1] % valeurs[i] == 0 && !grille[x][y]){
                    grille[x][y] = valeurs[i];
                    if(y != taille_m) explorer(x,y + 1);
                    else explorer(x + 1,1);
                    grille[x][y] = 0;
                }
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    while(cin >> taille_n >> taille_m) {
        solutions = 0;
        memset(grille,0,sizeof(grille));
        grille[1][1] = 2018;
        explorer(1, 2);
        cout << solutions << endl;
    }
}

Voir le codeAprès analyce, on obtient la matrice suivante :

On observe que le nombre de solutions suit la relation : mat[i][j] = mat[j][i]. De plus, chaque élément semble être un carré parfait. La régularité est donc dans cette propriété.

L'énoncé indique une relation entre a[i][j] et a[i-1][j], a[i][j-1]. On déduit alors que : mat[i][j] = (√mat[i-1][j] + √mat[i][j-1] + 1)²

Pour smiplifier davantage le code, on peut travailler avec les valeurs sous la racine carrée, où la réponse finale sera le carré de cette valeur.

Ainsi, la relation devient : mat[i][j] = mat[i][j-1] + mat[i-1][j] + 1; resultat = pow( mat[i][j] )

Code optimisé :

#include<bits/stdc++.h>
using namespace std;
#define Pour(i,a,b) for(int i = a; i <= b; i++)
#define int long long
const int mod = 1e9 + 7;
const int maxn = 2e3 + 10;
int matrice[maxn][maxn],lignes,colonnes;
signed main(){
    ios::sync_with_stdio(0);
    Pour(i,1,2000) matrice[1][i] = matrice[i][1] = i;
    Pour(i,2,2000) Pour(j,2,2000)
    matrice[i][j] = (matrice[i][j - 1] + matrice[i - 1][j] + 1) % mod;
    while(cin >> lignes >> colonnes)
        cout << matrice[lignes][colonnes] * matrice[lignes][colonnes] % mod << endl;
    return 0;
}

Voir le code