昨天上随机信号分析讲马氏链的时候突然想到这题的解法，今天写一下

定义矩阵A，Ans=A^n,令A[i][j]表示，经过1次变换后，第i个位置上的机器人位于第j个位置的情况数，则Ans[i][j]表示最初在第i个位置上的机器人n次变换后位于第j个位置的情况数

最后求一下任意两个机器人不在相同位置的情况数之和（注意乘法原理和加法原理的应用）

#include
     
      using namespace std;typedef long long LL;const int N=4;const LL mod=1e9+7;LL hh[N][N]= {
   {
   0,1,1,1},    {
    1,0,1,1},    {
    1,1,0,1},    {
    1,1,1,0}};struct Mat{    LL mat[N][N];    Mat()    {        memset(mat,0,sizeof(mat));    }    LL* operator [](int x)    //注意这种写法    {        return mat[x];    }} A;Mat Mut(Mat a,Mat b){    Mat c;    for(int k=0; k
      
       >=1)    {        if(n&1) c=Mut(c,a);        a=Mut(a,a);    }    return c;}void init_A(){    for(int i=0; i
       
        >n)    {        Mat Ans=Qpow(A,n);        LL sum=0;        for(int i1=0; i1<4; i1++)            for(int i2=0; i2<4; i2++)                for(int i3=0; i3<4; i3++)                    for(int i4=0; i4<4; i4++)                        if(i1!=i2&&i1!=i3&&i1!=i4&&i2!=i3&&i2!=i4&&i3!=i4)                        {                            sum+=Ans[0][i1]*Ans[1][i2]%mod*Ans[2][i3]%mod*Ans[3][i4]%mod;                            sum%=mod;                        }        cout<
        
         <