http://acdream.info/problem?pid=1093
女神的正多面体
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 128000/64000 KB (Java/Others)
Problem Description
EOF女神灰常喜欢整齐的东西，例如多面体中最喜欢的就是正多面体。正多面体的定义为：指每个面都是全等的正多边形的多面体。欧拉大人告诉我们，正多面体只有正四面体（正三棱锥），正六面体（立方体），正八面体（钻石？），正十二面体，还有正二十面体。后面两种太复杂了，EOF女神不喜欢。下面是前三种多面体的图片，EOF女神给每个多面体的每个顶点都编号了。
EOF女神想知道，如果从其中一个点出发，每一步可以沿着棱走到另一个顶点，k步之内从到达指定的顶点有多少种走法？（P.S.路径中只要有一个顶点不一样即视为不同的走法）。EOF女神知道结果会很庞大，因此只要知道除以1000000007的余数就可以了。
Input
先输入一个正整数T，表示测试数据的组数。
接下来是T行，每行包括四个正整数n,k,i,j,其中n∈{4,6,8},表示正多面体的种类，i为起点的编号，j为终点的编号，k为步数(k<=10^18)
Output
输出T行，每行输出一个整数，表示方法数。(记得要取余哦~)
Sample Input
3 6 1 8 4 6 2 3 1 8 3 2 4
Sample Output
1 2 12
Hint
第二组样例，有3->2->1与3->4->1两种方法
第三组样例，有2->1->4、2->3->4、2->5->4、2->6->4、2->1->3->4、2->1->5->4、2->3->1->4、2->3->6->4、2->5->1->4、2->5->6->4、2->6->3->4、2->6->5->4这12种方法
Source
mathlover
Manager
#include<iostream> #include<stdio.h> #include<cstring> #include<cstdlib> using namespace std; typedef long long LL; const LL p = 1000000007; struct Matrix { LL mat[3][9][9]; void init(int x,int n) { int i,j; for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i==j)mat[x][i][j]=1; else mat[x][i][j]=0; } void mem(int x) { memset(mat[x],0,sizeof(mat[x])); } }; Matrix multiply(Matrix cur,Matrix ans,int x,int n) { Matrix now; now.mem(x); int i,j,k; for(i=1;i<=n;i++) { for(k=1;k<=n;k++) { if(cur.mat[x][i][k]==0)continue; for(j=1;j<=n;j++) { if(ans.mat[x][k][j]==0)continue; now.mat[x][i][j]=now.mat[x][i][j]+cur.mat[x][i][k]*ans.mat[x][k][j]; now.mat[x][i][j]%=p; } } } return now; } Matrix add(Matrix cur,Matrix ans,LL x,LL n) { Matrix now; now.mem(x); int i,j; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { now.mat[x][i][j]=ans.mat[x][i][j]+cur.mat[x][i][j]; if(now.mat[x][i][j]>=p) now.mat[x][i][j]-=p; } } return now; } void solve(Matrix hxl,LL n,LL len,LL x,LL st,LL ed) { Matrix p1=hxl,p2=hxl,ret; ret.init(x,len); LL dp[64],dlen=0,i; while(n) { dp[++dlen]=(n&1); n=n>>1; } for(i=dlen-1;i>=1;i--) { p1=multiply(p1,add(p2,ret,x,len),x,len); p2=multiply(p2,p2,x,len); if(dp[i]==1) { p2=multiply(p2,hxl,x,len); p1=add(p2,p1,x,len); } } printf("%lld ",p1.mat[x][st][ed]); } int main() { int T,i,j; LL n,k,st,ed; scanf("%d",&T); while(T--) { scanf("%lld%lld%lld%lld",&n,&k,&st,&ed); if(n==4) { Matrix hxl; memset(hxl.mat,0,sizeof(hxl.mat)); for(i=1;i<=4;i++) for(j=1;j<=4;j++) { if(i==j)continue; hxl.mat[0][i][j]=1; } solve(hxl,k,4,0,st,ed); } else if(n==6) { Matrix hxl; memset(hxl.mat,0,sizeof(hxl.mat)); hxl.mat[1][1][2]=1;hxl.mat[1][1][4]=1;hxl.mat[1][1][5]=1; hxl.mat[1][2][1]=1;hxl.mat[1][2][3]=1;hxl.mat[1][2][6]=1; hxl.mat[1][3][2]=1;hxl.mat[1][3][4]=1;hxl.mat[1][3][7]=1; hxl.mat[1][4][1]=1;hxl.mat[1][4][3]=1;hxl.mat[1][4][8]=1; hxl.mat[1][5][1]=1;hxl.mat[1][5][6]=1;hxl.mat[1][5][8]=1; hxl.mat[1][6][2]=1;hxl.mat[1][6][5]=1;hxl.mat[1][6][7]=1; hxl.mat[1][7][3]=1;hxl.mat[1][7][6]=1;hxl.mat[1][7][8]=1; hxl.mat[1][8][4]=1;hxl.mat[1][8][5]=1;hxl.mat[1][8][7]=1; solve(hxl,k,8,1,st,ed); } else if(n==8) { Matrix hxl; memset(hxl.mat,0,sizeof(hxl.mat)); hxl.mat[2][1][2]=1;hxl.mat[2][1][3]=1;hxl.mat[2][1][4]=1;hxl.mat[2][1][5]=1; hxl.mat[2][2][1]=1;hxl.mat[2][2][3]=1;hxl.mat[2][2][5]=1;hxl.mat[2][2][6]=1; hxl.mat[2][3][1]=1;hxl.mat[2][3][2]=1;hxl.mat[2][3][4]=1;hxl.mat[2][3][6]=1; hxl.mat[2][4][1]=1;hxl.mat[2][4][3]=1;hxl.mat[2][4][5]=1;hxl.mat[2][4][6]=1; hxl.mat[2][5][1]=1;hxl.mat[2][5][2]=1;hxl.mat[2][5][4]=1;hxl.mat[2][5][6]=1; hxl.mat[2][6][2]=1;hxl.mat[2][6][3]=1;hxl.mat[2][6][4]=1;hxl.mat[2][6][5]=1; solve(hxl,k,6,2,st,ed); } } return 0; }