题解(附带递推公式推导过程)

#include<iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    long long f[51];
    f[2]=5;
    for(int i=3;i<=n;i++) f[i]=f[i-1]*2-1;
    /*
    递推过程
    和为偶数只有1+3,1+1,2+2,3+3
    两个格子时，有13,31,11,22,33
    三个格子时，原来末尾是1和3的每个都有两种，而末尾为2的只有一种
    原来末尾为1和3只会继续产生末尾为1和3的，而末尾为2的只会产生末尾为2的
    而末尾为二的永远只有一种，即n个2
    所以f[i]=2*(f[i-1]-1)+1=f[i-1]*2-1
    */
    cout<<f[n];
}