【BZOJ 4128】 matrix

题目其实很简单,BSGS可以一眼看出来,但这就需要矩阵求逆,然而我并不会。。。

于是发现了一种BSGS的非求逆方法,借此介绍一下。

aix?y=b(modP)

推出

aix=b?ay(modP)

因此我们只需要对每个b?ayhash一下就好了,然后穷举i,验证是否存在即可。code:

#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
int n,P;
struct hp{
    int num[71][71];
    bool operator < (const hp& a)const
      {
        int i,j;
        for (i=1;i<=n;++i)
          for (j=1;j<=n;++j)
            {
              if (num[i][j]<a.num[i][j]) return true;
              if (num[i][j]>a.num[i][j]) return false;
            }
        return false;
      }
    bool operator > (const hp& a)const
      {
        int i,j;
        for (i=1;i<=n;++i)
          for (j=1;j<=n;++j)
            {
              if (num[i][j]<a.num[i][j]) return false;
              if (num[i][j]>a.num[i][j]) return true;
            }
        return false;
      }
    bool operator == (const hp& a)const
      {
        int i,j;
        for (i=1;i<=n;++i)
          for (j=1;j<=n;++j)
            {
              if (num[i][j]<a.num[i][j]) return false;
              if (num[i][j]>a.num[i][j]) return false;
            }
        return true;
      }
}a,b;
hp mult(hp a,hp b)
{
    hp c;int i,j,k;
    for (i=1;i<=n;++i)
      for (j=1;j<=n;++j)
        {
          c.num[i][j]=0;
          for (k=1;k<=n;++k)
            c.num[i][j]=(c.num[i][j]+a.num[i][k]*b.num[k][j])%P;
        }
    return c;
}
int bsgs()
{
    int i,j,m;
    hp e,mi,xi;
    map<hp,int>x;
    for (i=1;i<=n;++i)
      for (j=1;j<=n;++j)
        e.num[i][j]=b.num[i][j];
    m=(int)(sqrt(P)+0.5); x[e]=0;
    for (i=1;i<=m;++i)
      {
        e=mult(e,a);
        x[e]=i;
      }
    for (i=1;i<=n;++i)
      for (j=1;j<=n;++j)
        {
          mi.num[i][j]=0;
          if (i==j)
            mi.num[i][j]=1;
        }
    for (i=1;i<=m;++i)
      mi=mult(mi,a);
    xi=mi;
    for (i=1;i<=m;++i)
      {
        if (x.count(mi)) return i*m-x[mi];
        mi=mult(mi,xi);
      }
}
int main()
{
    int i,j;
    scanf("%d%d",&n,&P);
    for (i=1;i<=n;++i)
      for (j=1;j<=n;++j)
        scanf("%d",&a.num[i][j]);
    for (i=1;i<=n;++i)
      for (j=1;j<=n;++j)
        scanf("%d",&b.num[i][j]);
    printf("%d\n",bsgs());
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

时间: 06-30

【BZOJ 4128】 matrix的相关文章

【BZOJ 2820】 YY的GCD

2820: YY的GCD Time Limit: 10 Sec  Memory Limit: 512 MB Submit: 807  Solved: 404 [Submit][Status] Description 神犇YY虐完数论后给傻×kAc出了一题 给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对 kAc这种傻×必然不会了,于是向你来请教-- 多组输入 Input 第一行一个整数T 表述数据组数 接下来T行,每行两个正整数,表示

【BZOJ 1854】 [Scoi2010]游戏

1854: [Scoi2010]游戏 Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 2609  Solved: 931 [Submit][Status] Description lxhgww最近迷上了一款游戏,在游戏里,他拥有很多的装备,每种装备都有2个属性,这些属性的值用[1,10000]之间的数表示.当他使用某种装备时,他只能使用该装备的某一个属性.并且每种装备最多只能使用一次. 游戏进行到最后,lxhgww遇到了终极boss,这个终极bos

【BZOJ 1036】【ZJOI 2008】树的统计

此题为树链剖分的裸题. 代码如下,使用常用的轻重链剖分. /************************************************************** Problem: 1036 User: Evensgn Language: C++ Result: Accepted Time:2468 ms Memory:5772 kb ****************************************************************/ #inc

【BZOJ 1150】 1150: [CTSC2007]数据备份Backup (贪心+优先队列)

1150: [CTSC2007]数据备份Backup Description 你在一家 IT 公司为大型写字楼或办公楼(offices)的计算机数据做备份.然而数据备份的工作是枯燥乏味 的,因此你想设计一个系统让不同的办公楼彼此之间互相备份,而你则坐在家中尽享计算机游戏的乐趣.已知办公 楼都位于同一条街上.你决定给这些办公楼配对(两个一组).每一对办公楼可以通过在这两个建筑物之间铺设网 络电缆使得它们可以互相备份.然而,网络电缆的费用很高.当地电信公司仅能为你提供 K 条网络电缆,这意味 着你仅

【BZOJ 2823】 [AHOI2012]信号塔

2823: [AHOI2012]信号塔 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 469  Solved: 198 [Submit][Status][Discuss] Description 在野外训练中,为了确保每位参加集训的成员安全,实时的掌握和收集周边环境和队员信息非常重要,集训队采用的方式是在训练所在地散布N个小型传感器来收集并传递信息,这些传感器只与设在集训地中的信号塔进行通信,信号塔接收信号的覆盖范围是圆形,可以接收到所有分布在

【BZOJ 3190】 [JLOI2013]赛车

3190: [JLOI2013]赛车 Time Limit: 10 Sec Memory Limit: 128 MB Submit: 803 Solved: 279 [Submit][Status][Discuss] Description 这里有一辆赛车比赛正在进行,赛场上一共有N辆车,分别称为个g1,g2--gn.赛道是一条无限长的直线.最初,gi位于距离起跑线前进ki的位置.比赛开始后,车辆gi将会以vi单位每秒的恒定速度行驶.在这个比赛过程中,如果一辆赛车曾经处于领跑位置的话(即没有其他

【BZOJ 2115】 [Wc2011] Xor

2115: [Wc2011] Xor Time Limit: 10 Sec  Memory Limit: 259 MB Submit: 962  Solved: 441 [Submit][Status] Description Input 第一行包含两个整数N和 M, 表示该无向图中点的数目与边的数目. 接下来M 行描述 M 条边,每行三个整数Si,Ti ,Di,表示 Si 与Ti之间存在 一条权值为 Di的无向边. 图中可能有重边或自环. Output 仅包含一个整数,表示最大的XOR和(十进

【BZOJ 1146】 [CTSC2008]网络管理Network

1146: [CTSC2008]网络管理Network Time Limit: 50 Sec  Memory Limit: 162 MB Submit: 1938  Solved: 577 [Submit][Status] Description M公司是一个非常庞大的跨国公司,在许多国家都设有它的下属分支机构或部门.为了让分布在世界各地的N个部门之间协同工作,公司搭建了一个连接整个公司的通信网络.该网络的结构由N个路由器和N-1条高速光缆组成.每个部门都有一个专属的路由器,部门局域网内的所有机

【BZOJ 2738】 矩阵乘法

2738: 矩阵乘法 Time Limit: 20 Sec Memory Limit: 256 MB Submit: 841 Solved: 351 [Submit][Status][Discuss] Description 给你一个N*N的矩阵,不用算矩阵乘法,但是每次询问一个子矩形的第K小数. Input 第一行两个数N,Q,表示矩阵大小和询问组数: 接下来N行N列一共N*N个数,表示这个矩阵: 再接下来Q行每行5个数描述一个询问:x1,y1,x2,y2,k表示找到以(x1,y1)为左上角.