样例过了,但wa+re,思路是暴力搜索
查看原帖
样例过了,但wa+re,思路是暴力搜索
889917
limingyuan333楼主2024/4/8 12:51
#include<bits/stdc++.h>
using namespace std;
long long div(long long a,long long b,long long p){
	return (a==1)?b:((b+(a-div(p%a,b%a,a))*p)/a%p);
}
long long gcd(long long x,long long y){
	if(y%x==0)
	return x;
	return gcd(y,x%y);
}
long long lcm(long long x,long long y){
	return x*y/gcd(x,y);
}
int dx[2]={0,1};
int dy[2]={1,0};
int n,m,xx,a[5010][5010],vis[5010][5010],pp[1000010],kk[1000010];
long long cnt=0;
void dfs(long long x,long long y,long long step,long long ans){
	if(x==n&&y==m){
		kk[++cnt]=ans,pp[cnt]=1<<step;
		return ;
	}
	for(int i=0;i<2;i++){
		int nx=dx[i]+x;
		int ny=dy[i]+y;
		if(!vis[nx][ny]){
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m){
				vis[nx][ny]=1;
				ans^=a[nx][ny];
				dfs(nx,ny,step+1,ans);
				ans^=a[nx][ny];
				vis[nx][ny]=0;	
			}
			else{
				kk[++cnt]=xx,pp[cnt]=1<<(step+1);
			}
		}	
	}
}
int main(){
	cin>>n>>m>>xx;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	 dfs(1,1,0,a[1][1]);
	// cout<<sum;
	 long long lcmmax=pp[1];
	 for(int i=2;i<=cnt;i++){
	 	if((pp[i]==0)||(lcmmax==0))
	 		continue;
	 	lcmmax=lcm(pp[i],lcmmax);
	 //	cout<<pp[i]<<' '<<kk[i]<<endl;
	 }
	 long long ans=0;
	 for(int i=1;i<=cnt;i++){
	 	if((pp[i]==0)||(kk[i]==0)){
	 		continue;
		 }
		long long k=lcmmax/pp[i];
	 	kk[i]*=k;
	 	ans+=kk[i];
	 }
	cout<<div(lcmmax,ans,1000000007);
	return 0;
}
2024/4/8 12:51
加载中...