CF630I题解

Grisses · 2022-08-07 20:51:30 · 题解

题面

一道水题，很符合题目的颜色。

对于连续的 n 辆车，在 2n-2 个车位里共有 (2n-2)-n+1=n-1 种放置方法。其中有两种是靠边的，为了保持连续的只有 n 个，我们在与连续的块相邻的车位只能放置另外 3 种车，而其他 n-3 个车位可以放任意车（显然不会再有连续的 n 辆车了）。一共是 2\times3\times4^{n-3} 种放置方法。对于另一种情况，有两个车位只能放置 3 种车，其他则可以放全部的 4 种，一共 (n-3)\times3^2\times4^{n-4} 种。加起来乘 4 就可以了。（每一种车都可以成为连续的那一种车）。

代码：

  #include<bits/stdc++.h>
  using namespace std;
  int n;
  long long ans;
  long long int fpow(long long int a,long long int b){
      long long int res=1;
      if(b<0)return 0;//特判
      while(b){
          if(b&1)res*=a;
          a*=a;
          b>>=1;
      }
      return res;
  }
  signed main()
  {
      scanf("%d",&n);
      ans=2LL*3*fpow(4LL,n-3)+(n-3)*9LL*fpow(4LL,n-4);
      printf("%lld",ans*4); 
      return 0;
  }