Niuke monthly race 14- simple counting

A

The question ：
It's for you. n A little bit , Just started in the 1 spot , Then I asked you what you were doing k Days come back 1 spot , You can walk freely in the middle , But there can't be two adjacent days with the same point . How many options do you have , And take the mold .

reflection ：
At the beginning, I thought about it and pushed it. I couldn't push it out , Then I thought dp, How about this one dp There are two states dp[i][0] On behalf of i Days and not 1 Number point ,dp[i][1] On behalf of i The day is at the first point , So the transfer is dp[i][0] = dp[i-1][1](n-1)+dp[i-1][0](n-2),dp[i][1] = dp[i-1][0]; If the title is given k The relatively small , Then you can do , however k It's too big , So we need to use matrix acceleration .

Code ：

 Matrix acceleration :
ll n,k;

ll dp[2][2];

ll a[2][2];
ll res[2][2];
ll tmp[2][2];

void mul(ll (&v1)[2][2],ll (&v2)[2][2]){
    
  rep(i,0,2){
    
    rep(j,0,2){
    
      tmp[i][j] = 0 ;
      rep(k,0,2){
    
        (tmp[i][j]+=v1[i][k]*v2[k][j])%=MOD;
      }
    }
  }
  rep(i,0,2){
    
    rep(j,0,2){
    
      v1[i][j]=tmp[i][j];
    }
  }
}

void mi(int m){
    
  a[0][0] = 0;
  a[0][1] = 1;
  a[1][0] = n-1;
  a[1][1] = n-2;

  res[0][0]=1;
  res[0][1]=0;
  res[1][0]=0;
  res[1][1]=1;

  while(m){
    
    if(m%2){
    
      mul(res,a);
    }
    mul(a,a);
    m/=2;
  }
}

int main(){
    
  cin>>n>>k;
  mi(k);
  cout<<res[0][0]<<endl;
  return 0;
}

summary ： Think more and summarize .