Submission #1001235

---

Source Code Expand

#pragma comment(linker, "/STACK:512000000")
#define _CRT_SECURE_NO_WARNINGS
//#include "testlib.h"
#include <bits/stdc++.h>
using namespace std;

#define all(a) a.begin(), a.end()
typedef long long li;
typedef long double ld;
void solve(bool);
void precalc();
clock_t start;
//int timer = 1;

int testNumber = 1;

bool todo = true;

int main() {
#ifdef AIM
    freopen("/home/alexandero/ClionProjects/ACM/input.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
#else
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    start = clock();
    int t = 1;
    cout.sync_with_stdio(0);
    cin.tie(0);
    precalc();
    cout.precision(10);
    cout << fixed;
    //cin >> t;
    int testNum = 1;
    while (t--) {
        //cerr << testNum << endl;
        //cout << "Case #" << testNum++ << ": ";
        solve(true);
        ++testNumber;
        //++timer;
    }

    /*while (true) {
        solve(false);
    }*/

#ifdef AIM
    cerr << "\n\n time: " << (clock() - start) / 1.0 / CLOCKS_PER_SEC << "\n\n";
#endif

    return 0;
}

//BE CAREFUL: IS INT REALLY INT?

template<typename T>
T binpow(T q, T w, T mod) {
    if (!w)
        return 1 % mod;
    if (w & 1)
        return q * 1LL * binpow(q, w - 1, mod) % mod;
    return binpow(q * 1LL * q % mod, w / 2, mod);
}

template<typename T>
T gcd(T q, T w) {
    while (w) {
        q %= w;
        swap(q, w);
    }
    return q;
}
template<typename T>
T lcm(T q, T w) {
    return q / gcd(q, w) * w;
}

void precalc() {

}

#define int li

const int mod = 1000000007;

int dp[310][310][310];

void add(int& cur, int add) {
    cur += add;
    if (cur >= mod) {
        cur -= mod;
    }
}

vector<vector<int>> get_from_mask(int mask, int n) {
    vector<vector<int>> res(n, vector<int>(n));
    for (int  i= 0; i < n; ++i) {
        for (int j = 0 ;j < n; ++j) {
            res[i][j] = (mask & 1);
            mask >>= 1;
        }
    }
    return res;
}

vector<vector<int>> mult(vector<vector<int>> a, vector<vector<int>> b, int n) {
    vector<vector<int>> res(n, vector<int>(n));
    for (int  i= 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < n; ++k) {
                res[j][i] ^= (a[i][k] * b[k][j]);
            }
        }
    }
    return res;
}

void solve(bool read) {
    int n;
    if (read) {
        cin >> n;
    }
    else {
        n = 2;
    }
    vector<vector<int>> matrix(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (read) {
                cin >> matrix[j][i];
            }
            else {
                matrix[i][j] = rand() % 2;
            }
        }
    }

    auto old = matrix;

    vector<int> nums;
    vector<int> first_bit;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < nums.size(); ++j) {
            if (matrix[i][first_bit[j]]) {
                for (int r = 0; r < n; ++r) {
                    matrix[i][r] ^= matrix[nums[j]][r];
                }
            }
        }
        for (int j = 0; j < n; ++j) {
            if (matrix[i][j]) {
                nums.push_back(i);
                first_bit.push_back(j);
                break;
            }
        }
    }

    vector<int> new_rank(n, 0);
    for (int x : nums) {
        new_rank[x] = 1;
    }

    vector<int> powers(n + 1, 1);
    for (int i = 1; i < powers.size(); ++i) {
        powers[i] = powers[i - 1] * 2 % mod;
    }

    memset(dp, 0, sizeof dp);
    dp[0][0][0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int r = 0; r <= i; ++r) {
            for (int rem = 0; rem + r <= i; ++rem) {
                if (new_rank[i]) {
                    add(dp[i + 1][r + 1][rem], dp[i][r][rem] * (powers[n] - powers[r + rem]) % mod);
                    continue;
                }
                add(dp[i + 1][r][rem], dp[i][r][rem] * powers[rem] % mod);
                add(dp[i + 1][r][rem + 1], dp[i][r][rem] * (powers[n] - powers[rem + r]) % mod);
            }
        }
    }

    int res = 0;
    for (int r = 0; r <= n; ++r) {
        for (int rem = 0; rem + r <= n; ++rem) {
            res += dp[n][r][rem] * binpow(powers[n - rem - r], n, mod) % mod;
            //cout << r << ' ' << rem << ' ' << dp[n][r][rem] << endl;
            res %= mod;
        }
    }

    if (res < 0) {
        res += mod;
    }
    cout << res << endl;


   /* int stupid_res = 0;
    for (int mask = 0; mask < (1 << (n * n)); ++mask) {
        auto a = get_from_mask(mask, n);
        for (int mask1 = 0; mask1 < (1 << (n * n)); ++mask1) {
            auto b = get_from_mask(mask1, n);
            if (mult(a, b, n) == old) {
                ++stupid_res;
            }
            else {

            }
        }
    }

    if (stupid_res != res) {
        cout << res << ' ' << stupid_res << endl;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                cout << old[i][j] << " ";
            }
            cout << endl;
        }
        exit(0);
    }*/


}

Submission Info

Judge Result