算法核心:矩阵建模,矩阵的快速幂
大意:已知有n只猫咪,开始时每只猫咪有花生米0颗,先有一组操作:
由下面三个中的k个操作组成:
g i 给i只猫咪一颗花生米
e i 让第i只猫咪吃掉它拥有的所有花生米
s i j 将猫咪i与猫咪j的拥有的花生米交换
现将上述操作做m次后,问每只猫咪有多少颗花生米?
分析:
因m的数据范围较大,用矩阵连乘。
构建矩阵模型,peanut[N] = {0,0,。。。。0,1}:即前n个数为0,最后一个数取1
matrix[N][N],初始化条件下为单位矩阵,。。。
对猫咪进行操作转化为在对矩阵peanut进行操作,一组操作过程转化为矩阵matrix,那么m次操作,即对peanut*(matrix^m)
EXP:
input:
316
g1
g2
g2
s12
g3
e2
初始化下矩阵:peanut
0001即每只猫咪的花生米个数为0
初始化下matrix为单位矩阵
1000
0100
0010
0001
经过操作
g1
给1号1颗花生米,即在第一列的最后一行加1
1000
0100
0010
1001
g2
1000
0100
0010
1101
g2
1000
0100
0010
1201
s12
//即交换第1,2列
0100
1000
0010
2101
g3
0100
1000
0010
2111
e2
//将第2列全部置为0
0000
1000
0010
2011
最后peanut=peanut*matrix*matrix.....*matrix=peanut*(matrix^m)故可用矩阵快速求幂
peanut的前n个数即为每只猫咪拥有的花生米数
-----------------------------------------------------------------------
P.S:
再说下几个要注意的地方:
(1):要注意在矩阵相乘的时候判断一下相乘的两个元素是否为0,否则会超时.
(2):要用__int64,结果超出了int型.
CODE:
- /*矩阵乘法*/
- /*AC代码:172ms*/
- #include <iostream>
- #define MAXN 105
- struct mat
- {
- __int64 v[MAXN][MAXN];
- mat()
- {memset(v,0,sizeof(v));}
- };
- mat e,ans;//e为转换矩阵,ans为e^M
- int N,M,K;
- mat matrix_mul(mat p1,mat p2)//矩阵乘法
- {
- mat t;
- int i,j,k;
- for(i=0;i<=N;i++)
- for(j=0;j<=N;j++)
- if(p1.v[i][j])//优化,不然会TLE
- for(k=0;k<=N;k++)
- t.v[i][k]+=(p1.v[i][j]*p2.v[j][k]);
- return t;
- }
- mat matrix_mi(mat p,int k)//矩阵快速幂
- {
- mat t;
- for(int i=0;i<=N;i++) t.v[i][i]=1;
- while(k)
- {
- if(k&1)
- t=matrix_mul(t,p);
- k>>=1;
- p=matrix_mul(p,p);
- }
- return t;
- }
- void Init()
- {
- int i,x,y,t;
- char w[2];
- memset(e.v,0,sizeof(e.v));
- for(i=0;i<=N;i++)//初始化e为单位矩阵
- e.v[i][i]=1;
- while(K--)
- {
- scanf("%s",w);
- if(w[0]=='g')//给一个
- {
- scanf("%d",&x);
- x--;//注意
- e.v[N][x]++;
- }
- else if(w[0]=='s')
- {
- scanf("%d%d",&x,&y);
- x--;y--;
- if(x!=y)
- {
- for(i=0;i<=N;i++)
- {t=e.v[i][x];e.v[i][x]=e.v[i][y];e.v[i][y]=t;}
- }
- }
- else
- {
- scanf("%d",&x);
- x--;
- for(i=0;i<=N;i++)
- e.v[i][x]=0;
- }
- }
- }
- int main()
- {
- int i,j;
- while(scanf("%d%d%d",&N,&M,&K)!=EOF)
- {
- if(N==0&&M==0&&K==0) break;
- Init();
- /*
- for(i=0;i<=N;i++)
- {
- for(j=0;j<=N;j++)
- printf("%d ",e.v[i][j]);
- printf("\n");
- }
- */
- ans=matrix_mi(e,M);
- int i;
- for(i=0;i<N;i++)//输出前N个即可
- printf("%I64d ",ans.v[N][i]);
- printf("\n");
- }
- return 0;
- }
相关推荐
经典算法 高效计算快速幂 使用矩阵方式进行计算
基于嵌入式与单片机的4乘4矩阵按键+8位数码管proteus设计实现
有关于 矩阵和智能的一个小的例子。。。。。。。。。。。。。。。。。顶替八月十五夜赠张功曹八月十五夜赠张功曹
2017年电子设计大赛_滚球控制系统源代码(PIXY+ds3115舵机+stm32+矩阵按键+lcd12864)
yxy版c++教程 浅谈矩阵快速幂
矩阵快速幂的模板,需要自己根据实际题目更改矩阵大小和数据类型,以免WA和TLE。经过矩阵乘法上的稀疏矩阵优化和int64的乘法取模幂优化,效率应该比较高。视情况使用mult()函数或直接使用乘法。代码中每个函数有注释...
c++ 矩阵快速幂封装支持矩阵乘法取模等
关于矩阵构造与快速幂的算法介绍与教程。。
斐波那契矩阵快速幂模版
由4x4矩阵键盘+51单片机+红外发射头组成的红外发射器电路原理图和PCB
矩阵乘法必用算法快速幂基础程序pascal
计算机视觉中的p矩阵组成以及QR分解内容
解矩阵方程+矩阵乘法,已封装,可直接调用, // private static double[][] matrixC ; /** * * 解矩阵方程 * * @param A * 矩阵 * @param b * 列阵 * @return matrixC 列阵 */ /** * * 矩阵相乘 * ...
快速幂和矩阵快速幂1
矩阵计算器+科学计算器的结合,支持最高五阶矩阵计算分析,能够计算矩阵的加、减、乘、逆、转置、秩、特征值等
4*4矩阵键盘+1602液晶显示的proteus仿真实验
逆矩阵CC++_C_C++_下载.zip
矩阵理论+Matrix+Theory,共700百多页,为英文原版。
计算机科学技术张宏伟;矩阵答案+大连理工大学矩阵与数值分析习题集计算机科学计算
矩阵键盘+数码管密码锁