gcd(ab,k)=gcd(gcd(a,k)times gcd(b,k),k)
设f[i][j]表示前i行，与k的gcd为j的方案数，h[i]表示当前行选一个或两个，乘积与k的gcd为i的方案数，然后DP即可。
时间复杂度O(N(M K))。
代码语言：javascript复制#include<cstdio>
#define N 165
typedef long long ll;
int n,m,K,L,i,j,k,d,a[N],id[200005],g[N][N],c[N],h[N],f[205][N];
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10) =c-'0';}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline void up(int&x,int y){x=(x y)%L;}
int main(){
read(n),read(m),read(K),read(L);
for(i=1;i<=K;i )if(K%i==0)a[ d]=i,id[i]=d;
for(i=1;i<=d;i )for(j=1;j<=d;j )g[i][j]=id[gcd(1LL*a[i]*a[j],K)];
for(f[0][1]=i=1;i<=n;i ){
for(j=1;j<=d;j )c[j]=h[j]=0;
for(j=1;j<=m;j )read(k),c[id[gcd(k,K)]] ;
for(j=1;j<=d;j )up(h[j],c[j]);
if(i>1&&i<n){
for(j=1;j<=d;j )up(h[g[j][j]],c[j]*(c[j]-1));
for(j=1;j<=d;j )for(k=1;k<j;k )up(h[g[j][k]],c[j]*c[k]*2);
}
for(j=1;j<=d;j )for(k=1;k<=d;k )up(f[i][g[j][k]],f[i-1][j]*h[k]);
}
return printf("%d",f[n][d]),0;
}发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/109218.html原文链接：https://javaforall.cn
