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
Submission Time |
|
Task |
H - AB=C Problem |
User |
Kostroma |
Language |
C++14 (GCC 5.4.1) |
Score |
1500 |
Code Size |
5257 Byte |
Status |
AC |
Exec Time |
284 ms |
Memory |
234496 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1500 / 1500 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example0.txt, example1.txt |
All |
000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, example0.txt, example1.txt |
Case Name |
Status |
Exec Time |
Memory |
000.txt |
AC |
235 ms |
232960 KB |
001.txt |
AC |
235 ms |
232960 KB |
002.txt |
AC |
236 ms |
232960 KB |
003.txt |
AC |
236 ms |
232960 KB |
004.txt |
AC |
233 ms |
232960 KB |
005.txt |
AC |
235 ms |
232960 KB |
006.txt |
AC |
236 ms |
232960 KB |
007.txt |
AC |
236 ms |
232960 KB |
008.txt |
AC |
235 ms |
232960 KB |
009.txt |
AC |
236 ms |
232960 KB |
010.txt |
AC |
235 ms |
232960 KB |
011.txt |
AC |
236 ms |
232960 KB |
012.txt |
AC |
237 ms |
232960 KB |
013.txt |
AC |
235 ms |
232960 KB |
014.txt |
AC |
237 ms |
233216 KB |
015.txt |
AC |
242 ms |
233216 KB |
016.txt |
AC |
237 ms |
233088 KB |
017.txt |
AC |
255 ms |
233728 KB |
018.txt |
AC |
237 ms |
233088 KB |
019.txt |
AC |
236 ms |
232960 KB |
020.txt |
AC |
244 ms |
233344 KB |
021.txt |
AC |
281 ms |
234368 KB |
022.txt |
AC |
236 ms |
233088 KB |
023.txt |
AC |
276 ms |
234368 KB |
024.txt |
AC |
279 ms |
234496 KB |
025.txt |
AC |
283 ms |
234496 KB |
026.txt |
AC |
284 ms |
234496 KB |
027.txt |
AC |
281 ms |
234496 KB |
028.txt |
AC |
277 ms |
234496 KB |
029.txt |
AC |
284 ms |
234496 KB |
030.txt |
AC |
284 ms |
234496 KB |
031.txt |
AC |
282 ms |
234496 KB |
032.txt |
AC |
275 ms |
234496 KB |
033.txt |
AC |
284 ms |
234496 KB |
034.txt |
AC |
276 ms |
234496 KB |
035.txt |
AC |
258 ms |
233856 KB |
036.txt |
AC |
278 ms |
234496 KB |
037.txt |
AC |
270 ms |
234240 KB |
038.txt |
AC |
276 ms |
234368 KB |
039.txt |
AC |
275 ms |
234368 KB |
example0.txt |
AC |
237 ms |
232960 KB |
example1.txt |
AC |
234 ms |
232960 KB |