截至写博客为止，貌似这是网上第一个采用数学公式来处理的。
网上的题解都是DFS或是动态规划，但感觉可以推公式直接用数学的方法处理，想了好久，终于推出公式。
题意：一个长度为n的由数字1,2,3,4 组成的序列，求至少有一对1,4相邻且2或3必须用上的方法数。
思路： 计A为有1，4相邻的方法数，B为有1,4相邻且无2,3的方法数，则答案为A - B
B很容易求，为2 ^ n - 2 ,再考虑A
计f(n)为有1,4相邻的方法数，g(n)为无1,4相邻但以1，或4开头的方法数
长度为n - 1且有1,4相邻的序列，后面接上1,2,3,4,仍然有1,4相邻，无1,4相邻但以1,4开头前面加上1,4 ，变成有1,4相邻的序列，故有递推公式
f[n] = 4 * f[n - 1 ] + g[n - 1]
考虑g(n) ，1或4后面是2,3，方法数为2 * 2 *(4 ^(n - 2) - f(n - 2)),或者1或4后面数与他相同，则变成一个字问题，方法数为g(n - 1),故
g(n) = 2 * 2 *(4 ^(n - 2) - f(n - 2)) + g(n - 1)
故可采取递推方式
代码如下：
1 #include<cstdio>
2 #include<iostream>
3 #include<cstdlib>
4 #include<cstring>
5 #include<string>
6 #include<algorithm>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<cmath>
11 using namespace std;
12 typedef long long LL;
13 const int N = 1008, INF = 0x3F3F3F3F;
14 LL f[N], g[N];
15 int main(){
16 f[1] = 0;
17 f[2] = 2;
18 g[1] = 2;
19 g[2] = 6;
20 for(int i = 3; i <= 17 ; i++){
21 f[i] = 4 * f[i - 1 ] + g[i - 1];
22 g[i] = (1 <<(2 * i - 2)) - 4 * f[i - 2] + g[i - 1];
23 }
24 int n;
25 while(~scanf("%d", &n) && n != -1){
26 printf("%d: %I64d ",n, f[n] - (1 << n) + 2);
27
28 }
29
30 return 0;
2 #include<iostream>
3 #include<cstdlib>
4 #include<cstring>
5 #include<string>
6 #include<algorithm>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<cmath>
11 using namespace std;
12 typedef long long LL;
13 const int N = 1008, INF = 0x3F3F3F3F;
14 LL f[N], g[N];
15 int main(){
16 f[1] = 0;
17 f[2] = 2;
18 g[1] = 2;
19 g[2] = 6;
20 for(int i = 3; i <= 17 ; i++){
21 f[i] = 4 * f[i - 1 ] + g[i - 1];
22 g[i] = (1 <<(2 * i - 2)) - 4 * f[i - 2] + g[i - 1];
23 }
24 int n;
25 while(~scanf("%d", &n) && n != -1){
26 printf("%d: %I64d ",n, f[n] - (1 << n) + 2);
27
28 }
29
30 return 0;
31 }
采用数学方法，代码如此简洁