注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ4128]Matrix  

2015-06-20 16:21:17|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

4128: Matrix

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 48  Solved: 30
[Submit][Status][Discuss]

Description

给定矩阵A,B和模数p,求最小的x满足A^x = B (mod p)

Input

第一行两个整数n和p,表示矩阵的阶和模数,接下来一个n * n的矩阵A.接下来一个n * n的矩阵B

Output

输出一个正整数,表示最小的可能的x,数据保证在p内有解

Sample Input

2 7
1 1
1 0
5 3
3 2

Sample Output

4

HINT

对于100%的数据,n <= 70,p <=19997,p为质数,0<= A_{ij},B_{ij}< p 保证A有逆

Solution

直接BSGS+hash就好了并不要求逆。
A^(kx-b)=B
A^kx=B*A^b

Code

/**************************************************************
    Problem: 4128
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:1364 ms
    Memory:3612 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#include<map>
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
int n,p,k;ll c[70][70];
struct M{int m[70][70];}a,b,tmp,t;
bool operator<(const M&a,const M&b){
    rep(i,n)rep(j,n)if(a.m[i][j]!=b.m[i][j])return a.m[i][j]<b.m[i][j];
    return 0;
}
M operator*(const M&a,const M&b){
    memset(c,0,sizeof(c));
    rep(i,n)rep(k,n)rep(j,n)c[i][j]+=a.m[i][k]*b.m[k][j];
    rep(i,n)rep(j,n)tmp.m[i][j]=c[i][j]%p;
    return tmp;
}
std::map<M,int>hash;main(){
    for(scanf("%d%d",&n,&p);k*k<=p;k++);k++;
    rep(i,n)rep(j,n)scanf("%d",&a.m[i][j]);
    rep(i,n)rep(j,n)scanf("%d",&b.m[i][j]);
    rep(i,n)t.m[i][i]=1;
    rep(i,k)hash[b]=i,b=b*a,t=t*a;a=t;
    for(int i=1;i<=k;i++){
        if(hash.count(a))return printf("%d\n",i*k-hash[a]);
        a=a*t;
    }
}
  评论这张
 
阅读(41)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018