首页 > 代码库 > poj 3735 大数量重复操作问题(矩阵快速幂)
poj 3735 大数量重复操作问题(矩阵快速幂)
题意:一个一维数组,3种操作: a: 第i个数+1,b: 第i个数=0 ,c::交换某俩处的数。 由三种基本操作构成一组序列,重复该序列m次(m<10^9),问结果
属于一种综合操作重复型: 每次乘以一矩阵T,相当于做一次操作。关键是构造这个矩阵。
先构造最初矩阵A : 1*(n +1) ={1,0,0,0...} , 第一个一时为了操作第一行数的,
T的构造:初始是N+1 * N+1单位阵 这样恰好操作第i个数, +1,就在第0行的第 i个加1;交换就对应列交换,清零就对应列清0.
ans= A*(T^m); 注意用;long long
#include<iostream> #include<cstring> using namespace std; struct juz { long long bat[105][105]; int x,y; //行 列 juz () { memset(bat,0,sizeof(bat)); x=0;y=0; } }; juz mutp(juz a,juz b) { juz c; c.x=a.x;c.y=b.y; memset(c.bat,0,sizeof(c.bat)); for(int k=0;k<a.y;k++) for(int i=0;i<a.x;i++) if(a.bat[i][k]) { for(int j=0;j<b.y;j++) { c.bat[i][j]+=(a.bat[i][k]*b.bat[k][j]); } } return c; } juz quickf(juz a,int k) { juz c=a; for(int i=0;i<a.x;i++) for(int j=0;j<a.x;j++) c.bat[i][j]=(i==j); while(k>=1) { if(k%2) c=mutp(c,a); k=k/2; a=mutp(a,a); } return c; } int main() { int n,m,k; while(cin>>n>>m>>k&&(n||m||k)) { juz a,b,c; a.x=1;a.y=n+1; b.x=n+1;b.y=n+1; for(int i=0;i<=n;i++) { a.bat[0][i]=0; b.bat[i][i]=1; } a.bat[0][0]=1; char tmp; int xx,yy; for(int i=0;i<k;i++) { cin>>tmp; if(tmp=='g') { cin>>xx; b.bat[0][xx]++; } else if(tmp=='e') { cin>>xx; for(int i=0;i<=n;i++) b.bat[i][xx]=0; } else { cin>>xx>>yy; for(int i=0;i<=n;i++) { int tx=b.bat[i][xx]; b.bat[i][xx]=b.bat[i][yy]; b.bat[i][yy]=tx; } } } c=quickf(b,m); c=mutp(a,c); for(int i=1;i<=n;i++) if(i!=n)cout<<c.bat[0][i]<<" "; else cout<<c.bat[0][i]<<endl; } return 0; }
poj 3735 大数量重复操作问题(矩阵快速幂)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。