把插头dp学了再回来看
通过连接得到6种状态之间的转移矩阵w[6][6]
$f[i][j] = sum_{k=0}^{5} f[i-1][k] * w[k][j]$
初始化
$f[1][1] = f[1][4] = 1$
终止
$f[n-1][0]+f[n-1][4]$
/*
插头dp
插法
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010, M = 1010;
int n;
int w[6][6] = {
{1, 0, 1, 1, 0, 0},
{0, 1, 0, 0, 1, 0},
{0, 1, 0, 0, 1, 0},
{0, 1, 0, 0, 1, 0},
{1, 0, 1, 1, 0, 1},
{0, 0, 0, 0, 1, 0},
};
int f[N][6][M];
void add(int a[], int b[])
{
for (int i = 0, t = 0; i < M; i ++ )
{
t += a[i] + b[i];
a[i] = t % 10;
t /= 10;
}
}
int main()
{
cin >> n;
f[1][1][0] = f[1][4][0] = 1;
for (int i = 2; i < n; i ++ )
for (int j = 0; j < 6; j ++ )
for (int k = 0; k < 6; k ++ )
if (w[k][j])
add(f[i][j], f[i - 1][k]);
int res[M] = {0};
add(res, f[n - 1][0]), add(res,f[n - 1][4]);
add(res, res);
int k = M - 1;
while (k > 0 && !res[k]) k -- ;
for (int i = k; i >= 0; i -- ) cout << res[i];
cout << endl;
return 0;
}
老实人大哥是真的猛