首页 > 代码库 > poj 3735 Training little cats 矩阵快速幂+稀疏矩阵乘法优化
poj 3735 Training little cats 矩阵快速幂+稀疏矩阵乘法优化
题目链接
题意：有n个猫，开始的时候每个猫都没有坚果，进行k次操作，g x表示给第x个猫一个坚果，e x表示第x个猫吃掉所有坚果，s x y表示第x个猫和第y个猫交换所有坚果，将k次操作重复进行m轮，问最后这n个猫各自有多少坚果。
题解：构造(n+1)*(n+1)的单位矩阵，data[i][j]表示第i个猫与第j个猫进行交换，最后一列的前n项就是每个猫的坚果数目，s操作就交换对应行，矩阵快速幂时间复杂度O(n^3*log2(m))会超时，我们注意到在n*n的范围内每一行只有一个1，利用稀疏矩阵的乘法优化可以优化时间复杂度至O(n^2*log2(m))。
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;struct matrix{ ll data[105][105];};matrix ma;ll n,m,k,x,y;matrix multi(matrix a,matrix b){ matrix c; memset(c.data,0,sizeof(c.data)); for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) { //稀疏矩阵的乘法优化 if(a.data[i][j]) //一个数一个数加进去 for(int k=0; k<=n; k++) //注意这里的ijk已经改变位置 c.data[i][k]+=a.data[i][j]*b.data[j][k]; } return c;}matrix init(matrix *a){ memset((*a).data,0,sizeof((*a).data)); for(int i=0;i<=n;i++) (*a).data[i][i]=1; //矩阵乘法的意义： //注意这里(*a).data[n][n]=1; 他的意义是继承上次操作的值 //(*a).data[i][j]=1;继承的是交换的值 两个值加起来就是新的值 return *a;}matrix pow1(matrix a,ll b){ matrix ans; init(&ans); while(b) { if(b&1) { ans=multi(ans,a); b--; } b>>=1; a=multi(a,a); } return ans;}void debug(matrix ans){ for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) printf("%lld%c",ans.data[i][j],j==n?‘\n‘:‘ ‘);}int main(){ while(scanf("%lld%lld%lld",&n,&m,&k)!=EOF) { if(n==0&&m==0&&k==0) break; char op[4]; init(&ma); while(k--) { scanf("%s%lld",op,&x); x--; if(op[0]==‘g‘) { ma.data[x][n]++; } else if(op[0]==‘s‘) { scanf("%lld",&y); y--; for(int i=0;i<=n;i++) swap(ma.data[x][i],ma.data[y][i]); } else if(op[0]==‘e‘) { for(int i=0;i<=n;i++) ma.data[x][i]=0; } } matrix ans=pow1(ma,m); //debug(ans); for(int i=0;i<n;i++) printf("%lld%c",ans.data[i][n],i==n-1?‘\n‘:‘ ‘); } return 0;}
poj 3735 Training little cats 矩阵快速幂+稀疏矩阵乘法优化
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。