每种状态最多只有三种后继状态：中间往左跳，中间往右跳，两边往中间跳。

如果把它们分别看成左儿子、右儿子、父亲的话，那么会得到一些二叉树。

取出起始状态和终止状态往上跳$k$步的所有状态，其他状态我们只关心它们到关键状态的距离。

于是设$dp[i][j][k]$表示从起始状态跳了$i$步，目前位于状态$j$子树内距离$j$深度为$k$的状态的方案数，然后DP即可。

时间复杂度$O(k^3)$。

 

#include
     
      #include
      
       using namespace std;const int N=110,P=1000000007;struct E{  long long v[3];  void read(){    scanf("%lld%lld%lld",&v[0],&v[1],&v[2]);    sort(v,v+3);  }  E left(){    E b;    for(int i=0;i<3;i++)b.v[i]=v[i];    b.v[1]=b.v[0]*2-b.v[1];    swap(b.v[0],b.v[1]);    return b;  }  E right(){    E b;    for(int i=0;i<3;i++)b.v[i]=v[i];    b.v[1]=b.v[2]*2-b.v[1];    swap(b.v[1],b.v[2]);    return b;  }  bool can(){    return v[0]+v[2]!=v[1]*2;  }  E up(){    E b;    for(int i=0;i<3;i++)b.v[i]=v[i];    if(v[1]-v[0]
       
        =P)x-=P;}inline int id(E b){  for(int i=1;i<=n;i++)if(a[i]==b)return i;  return 0;}inline void push(E b){if(!id(b))a[++n]=b;}int main(){  S.read();  T.read();  scanf("%d",&K);  for(push(now=S),i=1;i<=K;i++){    if(!now.can())break;    push(now=now.up());  }  for(push(now=T),i=1;i<=K;i++){    if(!now.can())break;    push(now=now.up());  }  for(i=1;i<=n;i++){    son[i][0]=id(a[i].left());    son[i][1]=id(a[i].right());    if(a[i].can())f[i]=id(a[i].up());  }  dp[0][id(S)][0]=1;  for(i=0;i
        
         <=n;j++)for(k=0;k<=K;k++)if(dp[i][j][k]){    for(t=0;t<2;t++)if(k)up(dp[i+1][j][k+1],dp[i][j][k]);    else{      if(son[j][t])up(dp[i+1][son[j][t]][0],dp[i][j][k]);      else up(dp[i+1][j][1],dp[i][j][k]);    }    if(k)up(dp[i+1][j][k-1],dp[i][j][k]);    else if(f[j])up(dp[i+1][f[j]][0],dp[i][j][k]);  }  return printf("%d",dp[K][id(T)][0]),0;}