63pts求调
查看原帖
63pts求调
1082999
jfls211320zhr楼主2024/10/23 17:10
#include<bits/stdc++.h>
using namespace std;
const int X=505,Y=1000007,Z=250,W=1023;
long long n,h,cnt,xnum;
long long ys[Z],ps[Y],g[X][X],dp[X][X][Z],gd[W][W];
long long gcd(long long x,long long y){
	if(!x)return y;
	if(!y)return x;
	if(x%y==0)return y;
	if(y%x==0)return x;
	if(x<W&&y<W)return gd[x][y];
	return gcd(y,x%y);
}
void svh20(){
	dp[1][1][g[1][1]%h]=1;
	for(long long i=1;i<=n;i++){
		for(long long ii=1;ii<=n;ii++){
			if(i==1&&ii==1)continue;
			if(g[i][ii]==-1)continue;
			for(long long iii=0;iii<h;iii++)dp[i][ii][iii*g[i][ii]%h]=(dp[i][ii][iii*g[i][ii]%h]+dp[i-1][ii][iii]+dp[i][ii-1][iii])%998244353;
		}
	}
	printf("%lld",dp[n][n][0]);
	return;
}
void svall(){
	dp[1][1][ps[gcd(g[1][1],h)]]=1;
	for(long long i=1;i<=n;i++){
		for(long long ii=1;ii<=n;ii++){
			if(i==1&&ii==1)continue;
			if(g[i][ii]==-1)continue;
			for(long long iii=1;iii<=xnum;iii++)dp[i][ii][ps[gcd(ys[iii]*g[i][ii],h)]]=(dp[i][ii][ps[gcd(ys[iii]*g[i][ii],h)]]+dp[i-1][ii][iii]+dp[i][ii-1][iii])%998244353;
		}
	}
	printf("%lld",dp[n][n][ps[h]]);
	return;
}
void init(){
	for(int i=1;i<=h;i++){
		if(h%i==0){
			xnum++;
			ys[xnum]=i;
			ps[i]=xnum;
		}
	}
	for(int i=1;i<W;i++)for(int ii=1;ii<W;ii++)gd[i][ii]=gd[ii][i]=__gcd(i,ii);
	return;
}
int main(){
	init();
	scanf("%lld %lld",&n,&h);
	for(long long i=1;i<=n;i++)for(long long ii=1;ii<=n;ii++)scanf("%lld",&g[i][ii]);
	if(h<=20)svh20();//数据分流 
	else svall();
	return 0;
}
2024/10/23 17:10
加载中...