acdream 1093 女神的正多面体

时间:2022-12-05 08:26:06

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女神给每个多面体的每个顶点都编号了。

acdream 1093 女神的正多面体

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 = ;
struct Matrix
{
LL mat[][][];
void init(int x,int n)
{
int i,j;
for(i=;i<=n;i++)
for(j=;j<=n;j++)
if(i==j)mat[x][i][j]=;
else mat[x][i][j]=;
}
void mem(int x)
{
memset(mat[x],,sizeof(mat[x]));
}
};
Matrix multiply(Matrix cur,Matrix ans,int x,int n)
{
Matrix now;
now.mem(x);
int i,j,k;
for(i=;i<=n;i++)
{
for(k=;k<=n;k++)
{
if(cur.mat[x][i][k]==)continue;
for(j=;j<=n;j++)
{
if(ans.mat[x][k][j]==)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=;i<=n;i++)
{
for(j=;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[],dlen=,i;
while(n)
{
dp[++dlen]=(n&);
n=n>>;
}
for(i=dlen-;i>=;i--)
{
p1=multiply(p1,add(p2,ret,x,len),x,len);
p2=multiply(p2,p2,x,len);
if(dp[i]==)
{
p2=multiply(p2,hxl,x,len);
p1=add(p2,p1,x,len);
}
}
printf("%lld\n",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==)
{
Matrix hxl;
memset(hxl.mat,,sizeof(hxl.mat));
for(i=;i<=;i++)
for(j=;j<=;j++)
{
if(i==j)continue;
hxl.mat[][i][j]=;
}
solve(hxl,k,,,st,ed);
}
else if(n==)
{
Matrix hxl;
memset(hxl.mat,,sizeof(hxl.mat));
hxl.mat[][][]=;hxl.mat[][][]=;hxl.mat[][][]=;
hxl.mat[][][]=;hxl.mat[][][]=;hxl.mat[][][]=;
hxl.mat[][][]=;hxl.mat[][][]=;hxl.mat[][][]=;
hxl.mat[][][]=;hxl.mat[][][]=;hxl.mat[][][]=;
hxl.mat[][][]=;hxl.mat[][][]=;hxl.mat[][][]=;
hxl.mat[][][]=;hxl.mat[][][]=;hxl.mat[][][]=;
hxl.mat[][][]=;hxl.mat[][][]=;hxl.mat[][][]=;
hxl.mat[][][]=;hxl.mat[][][]=;hxl.mat[][][]=;
solve(hxl,k,,,st,ed);
}
else if(n==)
{
Matrix hxl;
memset(hxl.mat,,sizeof(hxl.mat));
hxl.mat[][][]=;hxl.mat[][][]=;hxl.mat[][][]=;hxl.mat[][][]=;
hxl.mat[][][]=;hxl.mat[][][]=;hxl.mat[][][]=;hxl.mat[][][]=;
hxl.mat[][][]=;hxl.mat[][][]=;hxl.mat[][][]=;hxl.mat[][][]=;
hxl.mat[][][]=;hxl.mat[][][]=;hxl.mat[][][]=;hxl.mat[][][]=;
hxl.mat[][][]=;hxl.mat[][][]=;hxl.mat[][][]=;hxl.mat[][][]=;
hxl.mat[][][]=;hxl.mat[][][]=;hxl.mat[][][]=;hxl.mat[][][]=;
solve(hxl,k,,,st,ed);
}
}
return ;
}