BZOJ1172 : [Balkan2007]Dream

BZOJ1172 : [Balkan2007]Dream

$\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;
}

  

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/109218.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号