Submission #1290888
Source Code Expand
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
template<unsigned int mod_>
struct ModInt{
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr static uint mod = mod_;
uint v;
ModInt():v(0){}
ModInt(ll v):v(normS(v%mod+mod)){}
explicit operator bool() const {return v!=0;}
static uint normS(const uint &x){return (x<mod)?x:x-mod;} // [0 , 2*mod-1] -> [0 , mod-1]
static ModInt make(const uint &x){ModInt m; m.v=x; return m;}
ModInt operator+(const ModInt& b) const { return make(normS(v+b.v));}
ModInt operator-(const ModInt& b) const { return make(normS(v+mod-b.v));}
ModInt operator-() const { return make(normS(mod-v)); }
ModInt operator*(const ModInt& b) const { return make((ull)v*b.v%mod);}
ModInt operator/(const ModInt& b) const { return *this*b.inv();}
ModInt& operator+=(const ModInt& b){ return *this=*this+b;}
ModInt& operator-=(const ModInt& b){ return *this=*this-b;}
ModInt& operator*=(const ModInt& b){ return *this=*this*b;}
ModInt& operator/=(const ModInt& b){ return *this=*this/b;}
ll extgcd(ll a,ll b,ll &x,ll &y) const{
ll u[]={a,1,0},v[]={b,0,1};
while(*v){
ll t=*u/ *v;
rep(i,3) swap(u[i]-=t*v[i],v[i]);
}
if(u[0]<0) rep(i,3) u[i]=-u[i];
x=u[1],y=u[2];
return u[0];
}
ModInt inv() const{
ll x,y;
extgcd(v,mod,x,y);
return make(normS(x+mod));
}
bool operator==(const ModInt& b) const { return v==b.v;}
bool operator!=(const ModInt& b) const { return v!=b.v;}
friend istream& operator>>(istream &o,ModInt& x){
ll tmp;
o>>tmp;
x=ModInt(tmp);
return o;
}
friend ostream& operator<<(ostream &o,const ModInt& x){ return o<<x.v;}
};
using mint = ModInt<1000000007>;
const int MAX_N=300,MAX_M=300;
typedef bitset<MAX_N> Bs;
typedef vector<Bs> mat;
int getrank(int N, mat a){
int ans=0;
bool used[MAX_N]={};
rep(j,N){
int i=0;
while( (i < N) && (used[i] || !a[i][j]) ) i++;
if(i == N) continue;
ans++;
used[i] = 1;
rep(k,N) if(!used[k]&&a[k][j]){
a[k]^=a[i];
}
}
return ans;
}
mint dp[301][301][301];
mint p2[100001];
int main(){
int N;
cin>>N;
p2[0] = 1;
rep1(i,100000) p2[i] = p2[i-1]*2;
mat Cm(N);
rep(i,N){
rep(j,N){
int c;
cin>>c;
Cm[i][j] = c;
}
}
int C = getrank(N,Cm);
dp[0][0][0] = 1;
rep(i,N) rep(a,N) rep(c,N) if(dp[i][a][c]){
dp[i+1][a][c] += dp[i][a][c] * p2[a]; //already added
if(C>c) dp[i+1][a+1][c+1] += dp[i][a][c] * (p2[C+a-c]-p2[a]); //new in C
dp[i+1][a+1][c] += dp[i][a][c] * (p2[N]-p2[C+a-c]); //otherwise
}
mint ans = 0;
rep(a,N+1){
ans += dp[N][a][C] * p2[(N-a)*N];
}
cout<<ans<<endl;
}
Submission Info
Submission Time |
|
Task |
H - AB=C Problem |
User |
sigma425 |
Language |
C++14 (GCC 5.4.1) |
Score |
1500 |
Code Size |
3261 Byte |
Status |
AC |
Exec Time |
107 ms |
Memory |
107136 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 |
33 ms |
107136 KB |
001.txt |
AC |
33 ms |
107136 KB |
002.txt |
AC |
33 ms |
107136 KB |
003.txt |
AC |
33 ms |
107136 KB |
004.txt |
AC |
33 ms |
107136 KB |
005.txt |
AC |
33 ms |
107136 KB |
006.txt |
AC |
33 ms |
107136 KB |
007.txt |
AC |
33 ms |
107136 KB |
008.txt |
AC |
33 ms |
107136 KB |
009.txt |
AC |
33 ms |
107136 KB |
010.txt |
AC |
33 ms |
107136 KB |
011.txt |
AC |
33 ms |
107136 KB |
012.txt |
AC |
33 ms |
107136 KB |
013.txt |
AC |
34 ms |
107136 KB |
014.txt |
AC |
39 ms |
107136 KB |
015.txt |
AC |
40 ms |
107136 KB |
016.txt |
AC |
35 ms |
107136 KB |
017.txt |
AC |
49 ms |
107136 KB |
018.txt |
AC |
35 ms |
107136 KB |
019.txt |
AC |
33 ms |
107136 KB |
020.txt |
AC |
46 ms |
107136 KB |
021.txt |
AC |
97 ms |
107136 KB |
022.txt |
AC |
35 ms |
107136 KB |
023.txt |
AC |
84 ms |
107136 KB |
024.txt |
AC |
77 ms |
107136 KB |
025.txt |
AC |
107 ms |
107136 KB |
026.txt |
AC |
97 ms |
107136 KB |
027.txt |
AC |
98 ms |
107136 KB |
028.txt |
AC |
76 ms |
107136 KB |
029.txt |
AC |
100 ms |
107136 KB |
030.txt |
AC |
98 ms |
107136 KB |
031.txt |
AC |
100 ms |
107136 KB |
032.txt |
AC |
71 ms |
107136 KB |
033.txt |
AC |
94 ms |
107136 KB |
034.txt |
AC |
69 ms |
107136 KB |
035.txt |
AC |
53 ms |
107136 KB |
036.txt |
AC |
70 ms |
107136 KB |
037.txt |
AC |
64 ms |
107136 KB |
038.txt |
AC |
72 ms |
107136 KB |
039.txt |
AC |
71 ms |
107136 KB |
example0.txt |
AC |
33 ms |
107136 KB |
example1.txt |
AC |
33 ms |
107136 KB |