$\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))$。
#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.net/109218.html原文链接：https://javaforall.net
