Submission #2171314
Source Code Expand
#include<cstdio> #include<bitset> #include<algorithm> #include<cstring> using namespace std; const int mod=1000000007; int n; inline int getrank(bitset<300> c[300]) { int ans=0,i,j; for(i=0;i<n;++i) { for(j=ans;j<n;++j) { if(c[j][i]) { swap(c[j],c[i]); break; } } if(j==n) { continue; } for(j=ans+1;j<n;++j) { if(c[j][i]) { c[j]^=c[ans]; } } ++ans; } return ans; } int p2[90001]; inline void init(void) { int i; p2[0]=1; for(i=1;i<=90000;++i) { p2[i]=(p2[i-1]<<1)%mod; } return; } inline void clear(long long (*dp)[301]) { int i; for(i=0;i<=n;++i) { memset(dp[i],0,sizeof(long long)*(n+1)); } return; } long long dp1[301][301],dp2[301][301]; long long (*dp)[301]=dp1,(*dpt)[301]=dp2; int main() { init(); int i,j,k,x,r; bitset<300> c[300]; scanf("%d",&n); for(i=0;i<n;++i) { for(j=0;j<n;++j) { scanf("%d",&x); c[i][j]=x; } } r=getrank(c); // printf("%d\n",r); clear(dp); dp[0][0]=1; for(i=1;i<=n;++i)//放第几列 { clear(dpt); for(j=0;j<=n;++j)//已有维数 { for(k=0;k<=r;++k)//已包含c的维数 { dpt[j][k]+=(dp[j][k]*p2[j])%mod; if(j<n) { if(k<r) { dpt[j+1][k]+=(dp[j][k]*(p2[n]-p2[r-k+j]))%mod; dpt[j+1][k+1]+=(dp[j][k]*(p2[r-k]-1))%mod*p2[j]%mod; } else { dpt[j+1][k]+=(dp[j][k]*(p2[n]-p2[j]))%mod;; } } } } swap(dp,dpt); } long long ans=0; for(i=r;i<=n;++i) { ans=(ans+dp[i][r]*p2[n*(n-i)])%mod; } printf("%I64d",(ans%mod+mod)%mod); return 0; } /* 2 0 1 1 0 6 */ /* 10 1 0 0 1 1 1 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 1 1 1 0 0 0 0 1 0 1 0 0 1 1 1 1 1 741992411 */
Submission Info
Submission Time | |
---|---|
Task | H - AB=C Problem |
User | theyellowstar |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1919 Byte |
Status | WA |
Exec Time | 298 ms |
Memory | 2048 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:106:34: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘long long int’ [-Wformat=] printf("%I64d",(ans%mod+mod)%mod); ^ ./Main.cpp:63:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d",&n); ^ ./Main.cpp:68:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d",&x); ^
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | 2 ms | 768 KB |
001.txt | AC | 1 ms | 512 KB |
002.txt | AC | 1 ms | 512 KB |
003.txt | AC | 1 ms | 512 KB |
004.txt | AC | 1 ms | 512 KB |
005.txt | AC | 1 ms | 512 KB |
006.txt | AC | 1 ms | 512 KB |
007.txt | AC | 1 ms | 512 KB |
008.txt | AC | 1 ms | 512 KB |
009.txt | AC | 1 ms | 512 KB |
010.txt | AC | 1 ms | 512 KB |
011.txt | AC | 1 ms | 512 KB |
012.txt | AC | 1 ms | 512 KB |
013.txt | AC | 1 ms | 512 KB |
014.txt | WA | 17 ms | 1024 KB |
015.txt | AC | 8 ms | 1152 KB |
016.txt | AC | 4 ms | 896 KB |
017.txt | AC | 10 ms | 1536 KB |
018.txt | WA | 2 ms | 896 KB |
019.txt | AC | 1 ms | 640 KB |
020.txt | WA | 29 ms | 1280 KB |
021.txt | AC | 178 ms | 1920 KB |
022.txt | WA | 2 ms | 896 KB |
023.txt | AC | 58 ms | 1920 KB |
024.txt | WA | 298 ms | 2048 KB |
025.txt | WA | 162 ms | 1920 KB |
026.txt | WA | 254 ms | 1920 KB |
027.txt | AC | 127 ms | 1920 KB |
028.txt | WA | 60 ms | 1920 KB |
029.txt | WA | 181 ms | 1920 KB |
030.txt | AC | 199 ms | 1920 KB |
031.txt | WA | 231 ms | 1920 KB |
032.txt | WA | 26 ms | 1920 KB |
033.txt | WA | 268 ms | 1920 KB |
034.txt | AC | 22 ms | 1920 KB |
035.txt | AC | 13 ms | 1664 KB |
036.txt | AC | 298 ms | 1920 KB |
037.txt | AC | 236 ms | 1792 KB |
038.txt | AC | 27 ms | 1920 KB |
039.txt | AC | 280 ms | 1920 KB |
example0.txt | AC | 1 ms | 512 KB |
example1.txt | AC | 1 ms | 512 KB |