Submission #2119326


Source Code Expand

#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;

#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ldb ldouble

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 19;
int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<n;i++)
#define Se second
#define Fi first

const int MX = 300;
const int MM = 1000000007;

ll pw2[MX*MX];
int N;

ll DP[MX][MX][MX];
int C[MX][MX];

int main()
{
	pw2[0] = 1;
	for(int i = 1; i < MX*MX; i++) pw2[i] = pw2[i-1] * 2 % MM;
	scanf("%d", &N);
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++) scanf("%d", C[i]+j);
	}
	/*

	int tot = 0;

	for(int i = 0; i < 1<<N*N; i++){
		for(int j = 0; j < 1<<N*N; j++){
			int A[MX][MX] = {};
			for(int p = 0; p < N; p++){
				for(int q = 0; q < N; q++){
					for(int r = 0; r < N; r++){
						if( i&1<<p*N+q && j&1<<q*N+r ) A[p][r] ^= 1;
					}
				}
			}
			int ch = 1;
			for(int p = 0; p < N; p++){
				for(int q = 0; q < N; q++){
					if( A[p][q] != C[p+1][q+1] ) ch = 0;
				}
			}
			tot += ch;
		}
	}
	printf("%d\n", tot);
// */
	int K = 0, cur = 1;
	for(int i = 1; i <= N; i++){
		for(int j = cur; j <= N; j++){
			if( C[j][i] == 1 ){
				for(int k = 1; k <= N; k++) swap(C[j][k], C[cur][k]);
				break;
			}
		}
		if( C[cur][i] == 0 ) continue;
		for(int j = cur+1; j <= N; j++){
			if( !C[j][i] ) continue;
			for(int k = 1; k <= N; k++){
				C[j][k] ^= C[i][k];
			}
		}
		K++; cur++;
	}

	DP[0][0][0] = 1;
	for(int i = 1; i <= N; i++){
		for(int j = 0; j <= K; j++){
			for(int k = j; k <= N; k++){
				DP[i][j][k] = DP[i-1][j][k] * pw2[k] % MM;
				if( j && k ) DP[i][j][k] = (DP[i][j][k] + DP[i-1][j-1][k-1] * (pw2[K+(k-j)] - pw2[k-1] + MM)) % MM;
				if( k ) DP[i][j][k] = (DP[i][j][k] + DP[i-1][j][k-1] * (pw2[N] - pw2[K+k-1-j] + MM*2)) % MM;
//				printf("%d %d %d %lld\n", i, j, k, DP[i][j][k]);
			}
		}
	}
	ll ans = 0;
	for(int i = K; i <= N; i++){
//		printf("%d %d %d %lld\n", N, K, i, DP[N][K][i]);
		ans = (ans + DP[N][K][i] * pw2[(N-i)*N]) % MM;
	}
	printf("%lld\n", ans);
}

Submission Info

Submission Time
Task H - AB=C Problem
User zigui
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2928 Byte
Status WA
Exec Time 168 ms
Memory 211584 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:65:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
./Main.cpp:67:50: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   for(int j = 1; j <= N; j++) scanf("%d", C[i]+j);
                                                  ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1500
Status
AC × 2
AC × 23
WA × 19
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 2 ms 896 KB
001.txt AC 2 ms 1024 KB
002.txt AC 2 ms 1024 KB
003.txt AC 2 ms 1024 KB
004.txt AC 2 ms 1024 KB
005.txt AC 2 ms 3072 KB
006.txt AC 2 ms 3072 KB
007.txt AC 2 ms 3072 KB
008.txt AC 2 ms 3072 KB
009.txt AC 2 ms 3072 KB
010.txt AC 2 ms 3072 KB
011.txt AC 2 ms 3072 KB
012.txt AC 2 ms 3072 KB
013.txt AC 2 ms 3072 KB
014.txt WA 25 ms 81408 KB
015.txt WA 27 ms 87424 KB
016.txt AC 13 ms 50304 KB
017.txt AC 34 ms 146560 KB
018.txt WA 13 ms 48384 KB
019.txt AC 3 ms 7168 KB
020.txt WA 41 ms 108288 KB
021.txt AC 143 ms 208896 KB
022.txt WA 13 ms 50432 KB
023.txt AC 77 ms 206336 KB
024.txt WA 168 ms 211584 KB
025.txt WA 160 ms 211200 KB
026.txt WA 168 ms 211456 KB
027.txt WA 153 ms 211072 KB
028.txt WA 167 ms 211456 KB
029.txt WA 167 ms 211456 KB
030.txt WA 163 ms 211328 KB
031.txt WA 160 ms 211200 KB
032.txt WA 117 ms 210688 KB
033.txt WA 161 ms 211200 KB
034.txt WA 49 ms 210176 KB
035.txt AC 38 ms 165120 KB
036.txt WA 168 ms 211584 KB
037.txt AC 139 ms 196736 KB
038.txt WA 154 ms 210944 KB
039.txt WA 162 ms 209152 KB
example0.txt AC 2 ms 1024 KB
example1.txt AC 3 ms 7168 KB