Cod sursa(job #3233564)

Utilizator MirceaDonciuLicentaLicenta Mircea Donciu MirceaDonciuLicenta Data 3 iunie 2024 20:10:36
Problema Patrate2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int MOD = 1000000007;

// Function to calculate the number of valid matrices
long long countValidMatrices(int N) {
    vector<vector<long long>> dp(N + 1, vector<long long>(N + 1, 0));
    dp[0][0] = 1;

    for (int i = 1; i <= N; ++i) {
        dp[i][0] = dp[i - 1][0] * 2 % MOD;
    }
    for (int j = 1; j <= N; ++j) {
        dp[0][j] = dp[0][j - 1] * 2 % MOD;
    }
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + MOD) % MOD;
            dp[i][j] = dp[i][j] * 2 % MOD;
        }
    }

    return dp[N][N];
}

int main() {
    ifstream infile("patrate2.in");
    ofstream outfile("patrate2.out");

    int N;
    infile >> N;

    long long result = countValidMatrices(N);

    outfile << result << endl;

    infile.close();
    outfile.close();

    return 0;
}