题目描述

小生和小森在玩兔子之谜游戏。有三只兔子排成一排。知道每只兔子的初始位置，以及三个兔窝的位置。 

游戏的规则是，重复以下步骤k次：选择两个不同的兔子A和B，分别位于a和b。A可以跳过B到达2*b-a的点： 

 

跳跃是不允许其他小兔子已经在点2*b-a的位置上： 

 

跳跃也不允许一次跳过一个以上的兔子： 

 

现在小生和小森想要知道，k次操作之后，能否让所有兔子都分别跳到一个兔窝里面。注意，第i个兔子并不一定要在第i个巢。并且输出跳法的种数，数值可能很大，要对结果取模1000000007。只要有一个跳跃是不同的，两种方式被认为是不同的。

 

输入

有多组数据： 

第一行，包含一个整数Num，表示测试数据的个数。（1<=Num<=10） 

每组测试数据， 

第一行三个整数，第二行三个整数，分别表示兔子的初始位置和兔窝的位置。两组数值都是严格递增给出。范围均为[-10^18,10^18]。 

最后一个整数k。[1,100]。 

输出

共Num行， 

跳跃的种数。 

样例输入

8

0 5 8

0 8 11

1

0 5 8

0 8 11

3

0 5 8

0 8 11

2

5 8 58

13 22 64

58

0 1 2

1 2 3

100

5 8 58

20 26 61

58

67 281 2348

235 1394 3293

83

-1000000000000000000 999999999999999998 999999999999999999

-1000000000000000000 999999999999999999 1000000000000000000

5

样例输出

1

5

0

0

0

537851168

167142023

29

 

这道题一拿到不知道怎么做，好像只能DFS

但是接着我们发现，三只兔子有三种操作：两只兔子跳到中间（一种情况）；一只兔子跳到外面（两只兔子跳到外面）。

可以把兔子间的跳跃抽象成一个二插树形结构

根节点：三只兔子等距；两只兔子就跳不到中间啦

叶节点：中间那只兔子分别跳到左边和右边的情况

对于跳跃的方案数，只是询问在一棵二叉树上两个节点间之间用K步跳跃所能达到的方案数

我们用dp[i][j][k]表示初始节点A离LCA  i步，结束点B离LCA  j步，还剩下k步时的方案总数。为了方便处理，我们假设B节点不动（这很重要，也很巧妙）

当i>0时 让A向上下走dp[i][j][k]+=dp[i-1][j][k-1]+2*dp[i+1][j][k-1]

当i=0时 让A向上下走（向上走时LCA为A）dp[0][j][k]+=dp[0][j+1][k-1]+dp[0][j-1][k-1]+dp[1][j][k-1]

当i=j=0时 让A向上下走 dp[0][0][k]=dp[0][1][k-1]+dp[1][0][k-1]*2;

根据定义，j>B离LCA的距离时DP为0；代码借鉴自LHQ大神的blog

 

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef long long ll;#define mod 1000000007const int N=107;struct note{    int x,y,z;    friend bool operator ==(note a,note b)    {        return (a.x==b.x&&a.y==b.y&&a.z==b.z);    }}point,point1,fa[2][N];int dp[N][N][N];int k,deep_a,deep_b;bool ok(note s){    return (!(s.z-s.y==s.y-s.x));}note make(note s){    note r;    if(s.z-s.y
         
          k||j>deep_b) return 0;    if(dp[i][j][k]!=-1) return dp[i][j][k];    if(i>0&&j>0)    {        dp[i][j][k]=(DP(i+1,j,k-1)*2ll+DP(i-1,j,k-1))%mod;      }    else if (i==0&&j>0)      {          dp[i][j][k]=((ll)DP(1,j,k-1)+DP(0,j-1,k-1)+DP(0,j+1,k-1))%mod;         }      else if (i>0 && j==0)      {          dp[i][j][k]=(DP(i+1,0,k-1)*2ll+DP(i-1,0,k-1))%mod;      }      else if (i==0&&j==0)      {          dp[i][j][k]=(DP(1,0,k-1)*2ll+DP(0,1,k-1))%mod;      }      return dp[i][j][k];  }int main(){    int num;    scanf("%d",&num);    while(num--)    {        scanf("%lld %lld %lld",&point.x,&point.y,&point.z);        scanf("%lld %lld %lld",&point1.x,&point1.y,&point1.z);        scanf("%d",&k);        fa[0][0]=point;fa[1][0]=point1;        deep_a=deep_b=0;        for(int i=1;i<=k&&ok(fa[0][i-1]);i++)        {            fa[0][i]=make(fa[0][i-1]);            deep_a++;            }        for(int i=1;i<=k&&ok(fa[1][i-1]);i++)        {            fa[1][i]=make(fa[1][i-1]);            deep_b++;        }        bool flag=1;        int t1=-1,t2=-1;        for(int i=0;i<=deep_a&&flag;i++)            for(int j=0;j<=deep_b&&flag;j++)            {                if(fa[0][i]==fa[1][j])                {                    t1=i,t2=j;                    flag=false;                }            }        if(t1==-1)        {            cout<<0<