loj#6040. 「雅礼集训 2017 Day5」矩阵（线性代数+递推）

题面

题解

我的线代学得跟屎一样看题解跟看天书一样所以不要指望这题我会写题解

//minamoto

#include<bits/stdc++.h>

#define R register

#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)

#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)

#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

using namespace std;

char buf[1<<21],*p1=buf,*p2=buf;

inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}

int read(){

    R int res,f=1;R char ch;

    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);

    return ch-'0';

}

const int N=2005,P=1e9+7;

inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}

inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}

inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}

int ksm(R int x,R int y){

	R int res=1;

	for(;y;y>>=1,x=mul(x,x))if(y&1)res=mul(res,x);

	return res;

}

bitset<N>A[N];int f[N][N],bin[N],n,r,p,l,res;

int main(){

//	freopen("testdata.in","r",stdin);

	scanf("%d",&n);

	fp(i,1,n)fp(j,1,n)A[i][j]=read();

	fp(i,1,n){

		l=p=r+1;

		for(;l<=n&&!A[l][i];++l);if(l>n)continue;

		if(l!=p)swap(A[l],A[p]);

		fp(j,p+1,n)if(A[j][i])A[j]^=A[p];

		++r;

	}

	bin[0]=1;fp(i,1,n)bin[i]=mul(bin[i-1],2);

	f[0][0]=1;fp(i,1,n)fp(j,0,i)f[i][j]=add((j?mul(f[i-1][j-1],dec(bin[n],bin[j-1])):0),mul(f[i-1][j],bin[j]));

	fp(i,r,n)res=add(res,1ll*f[n][i]*f[i][r]%P*ksm(bin[n-i],n)%P);

	printf("%d\n",mul(res,ksm(f[n][r],P-2)));

	return 0;

}

巴特西

loj#6040. 「雅礼集训 2017 Day5」矩阵（线性代数+递推）

题面

题解

最新文章

热门文章