Submission #2093462
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;
#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------
int N,R;
const int MAT=402;
int mat[402][402];
ll dp[303][303][303];
ll p2[101010];
ll mo=1000000007;
int gf2_rank(int A[MAT][MAT],int n) { /* input */
int i,j,k;
FOR(i,n) {
int be=i,mi=n+1;
for(j=i;j<n;j++) {
FOR(k,n) if(A[j][k]) break;
if(k<mi) be=j,mi=k;
}
if(mi>=n) break;
FOR(j,n) swap(A[i][j],A[be][j]);
FOR(j,n) if(i!=j&&A[j][mi]) {
FOR(k,n) A[j][k] ^= A[i][k];
}
}
return i;
}
void solve() {
int i,j,k,l,r,x,y; string s;
p2[0]=1;
FOR(i,101000) p2[i+1]=p2[i]*2%mo;
cin>>N;
FOR(y,N) FOR(x,N) cin>>mat[y][x];
R=gf2_rank(mat,N);
dp[0][0][0]=1;
FOR(i,N) {
FOR(x,R+1) FOR(y,N-R+1) if(dp[i][x][y]) {
ll v=dp[i][x][y]*p2[x+y]%mo;
// no new rank
(dp[i+1][x][y]+=v)%=mo;
// common rank
if(x<R) (dp[i+1][x+1][y]+=v*(p2[R-x]+mo-1))%=mo;
// single rank
if(y<N-R) (dp[i+1][x][y+1]+=v*(p2[N-x-y]-p2[R-x]+mo))%=mo;
}
}
//FOR(x,R+1) FOR(y,N-R+1) cout<<x<<" "<<y<<" "<<dp[N][x][y]<<endl;
ll ret=0;
FOR(y,N-R+1) (ret+=dp[N][R][y]*p2[N*(N-R-y)])%=mo;
cout<<ret<<endl;
}
int main(int argc,char** argv){
string s;int i;
if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
cout.tie(0); solve(); return 0;
}
Submission Info
Submission Time |
|
Task |
H - AB=C Problem |
User |
kmjp |
Language |
C++14 (GCC 5.4.1) |
Score |
1500 |
Code Size |
1788 Byte |
Status |
AC |
Exec Time |
209 ms |
Memory |
216576 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 |
3 ms |
1024 KB |
001.txt |
AC |
3 ms |
1024 KB |
002.txt |
AC |
3 ms |
3072 KB |
003.txt |
AC |
3 ms |
3072 KB |
004.txt |
AC |
3 ms |
3072 KB |
005.txt |
AC |
3 ms |
3072 KB |
006.txt |
AC |
3 ms |
3072 KB |
007.txt |
AC |
3 ms |
3072 KB |
008.txt |
AC |
3 ms |
3072 KB |
009.txt |
AC |
3 ms |
3072 KB |
010.txt |
AC |
3 ms |
3072 KB |
011.txt |
AC |
3 ms |
3072 KB |
012.txt |
AC |
3 ms |
3072 KB |
013.txt |
AC |
3 ms |
3072 KB |
014.txt |
AC |
25 ms |
83200 KB |
015.txt |
AC |
29 ms |
89344 KB |
016.txt |
AC |
16 ms |
52352 KB |
017.txt |
AC |
36 ms |
148864 KB |
018.txt |
AC |
14 ms |
50304 KB |
019.txt |
AC |
4 ms |
7168 KB |
020.txt |
AC |
47 ms |
111872 KB |
021.txt |
AC |
199 ms |
214528 KB |
022.txt |
AC |
14 ms |
52352 KB |
023.txt |
AC |
119 ms |
210432 KB |
024.txt |
AC |
91 ms |
216576 KB |
025.txt |
AC |
209 ms |
216576 KB |
026.txt |
AC |
194 ms |
216576 KB |
027.txt |
AC |
197 ms |
216576 KB |
028.txt |
AC |
79 ms |
216576 KB |
029.txt |
AC |
208 ms |
216576 KB |
030.txt |
AC |
200 ms |
216576 KB |
031.txt |
AC |
207 ms |
216576 KB |
032.txt |
AC |
56 ms |
216576 KB |
033.txt |
AC |
173 ms |
216576 KB |
034.txt |
AC |
52 ms |
216576 KB |
035.txt |
AC |
41 ms |
169344 KB |
036.txt |
AC |
67 ms |
216576 KB |
037.txt |
AC |
60 ms |
200192 KB |
038.txt |
AC |
62 ms |
214528 KB |
039.txt |
AC |
73 ms |
214528 KB |
example0.txt |
AC |
3 ms |
3072 KB |
example1.txt |
AC |
4 ms |
7168 KB |