今天的 XY 题居然是递推专题，五道题目全都是递推，30+个人 AK 了……
递推是按照一定的规律来计算序列中的每个项，通常是通过计算前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。
"利用了计算机速度快和不知疲倦的机器特点" :no_mouth:
蛇皮目录
问题一
题目描述
在所有的 N 位数中，有多少个数中有偶数个数字 3？
Time Limit: 1000ms Memory Limit: 65536Bit
输入输出格式
读入一个数 N。
输出答案。由于结果可能很大，你只需要输出这个答案 mod 12345 的值。
样例输入
2
样例输出
73
数据范围
1<=N<=1000
问题分析
很明显是递推（或者说 DP）。容易想到定义 表示在 位数中有多少个数中有偶数个数字 3，但是这样如何进行状态转移呢？很明显，单纯这么定义无法直接状态转移。所以我们再定义 表示 位数中有多少个数字中有奇数个数字 3。
考虑状态转移，对于 和 ，肯定与 位数字的情况有关。先考虑 ：
- 如果第 位数字（也就是相较于 位，新增的一位数字）是 3，那么剩下的 位就应该有奇数个 3，方案数是 ；
- 如果第 位数字不是 3，则可以是除了 3 以外的 9 个数字，剩下的 位应当有偶数个 3，方案数：
同理可以得出 的状态转移。转移方程：
代码
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1005,tt=12345;
int n,f[maxn],g[maxn];
int main(){
scanf("%d",&n);
if (n==1) {printf("9\n");return 0;}
f[1]=8;g[1]=1;
for (int i=2;i<=n;i++){
f[i]=(f[i-1]*9%tt+g[i-1])%tt;
g[i]=(g[i-1]*9%tt+f[i-1])%tt;
}
printf("%d\n",f[n]);
return 0;
}
问题二
题目描述
用 1×1 和 2×2 的磁砖不重叠地铺满 N×3 的地板，共有多少种方案？
样例输入
2
样例输出
3
（数据范围、时空限制、输入输出格式同上）
问题分析
一看到这题可能会想到轮廓线 DP……其实根本没有这么复杂，注意到只有 1×1 和 2×2 两种地砖，那么对于每个 2×3 的矩形有两种情况：右边一块 2×2、左边两块 1×1 和 左边一块 2×2、右边两块 1×1。还有另一种情况就是每行三块 1×1。定义 表示铺 行的方案数，那么递推式很容易得出：
代码
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1005,tt=12345;
int n,f[maxn];
int main(){
scanf("%d",&n);
f[0]=1;
for (int i=1;i<=n;i++) f[i]=(f[i-2]*2%tt+f[i-1])%tt;
printf("%d\n",f[n]);
return 0;
}
问题三
题目描述
从原点出发，一步只能向右走、向上走或向左走。恰好走 N 步且不经过已走的点共有多少种走法？
样例输入
2
样例输出
7
（数据范围、时空限制、输入输出格式同上）
问题分析
一看这题，可能难点主要在“不经过已走的点”如何处理。如果我们定义 表示走了 i 步的方案数，那么“不经过已走的点”就没法处理了。 不妨定义 表示走了 i 步，最后一步向上/左/右走的方案数。那么上次是向右边走，这次就不能向左边走；上次向左，这次就不能向右。这样就可以直接进行状态转移了：
代码
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1005,tt=12345;
int n,f[maxn][3];
int main(){
scanf("%d",&n);
f[1][0]=f[1][1]=f[1][2]=1;
for (int i=2;i<=n;i++){
f[i][0]=(f[i-1][0]+f[i-1][1]+f[i-1][2])%tt;
f[i][1]=(f[i-1][0]+f[i-1][1])%tt;
f[i][2]=(f[i-1][0]+f[i-1][2])%tt;
}
printf("%d\n",(f[n][0]+f[n][1]+f[n][2])%tt);
return 0;
}
问题四
题目描述
圆周上有 N 个点。连接任意多条（可能是 0 条）不相交的弦（共用端点也算相交）共有多少种方案？
样例输入
4
样例输出
9
（数据范围、时空限制、输入输出格式同上）
问题分析
也是很显然的递推题……一般这种题目我们可以“找规律”：
-
如果只有 0 个点，无法连接，只有一种方案，即全部不连。。
-
同理，如果只有一个点，。
-
如果有两个点，要么连接，要么不连，。
-
（重头戏来了）如果有三个点，则新加入的点要么不与其他两个点连接（方案数：），要么随便选一个连接，“孤立”剩下的一个点，共 4 种方案。
-
（真正的重头戏）如果再加入一个点呢？
-
不与其他三个点连接，方案数
-
与某个点连接，可以看成连成的这条边把点集分成了两部分，左右两部分剩下的点分别连边，方案数分别相乘。
在上述手算过程中我们发现了规律，总结出递推式就是：
代码
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1005,tt=12345;
int n,f[maxn];
int main(){
scanf("%d",&n);
f[0]=f[1]=1;f[2]=2;
for (int i=3;i<=n;i++){
f[i]=f[i-1];
for (int j=0;j<=i-2;j++) f[i]=(f[i]+f[j]*f[i-j-2]%tt)%tt;
}
printf("%d\n",f[n]);
return 0;
}
问题五
题目描述
在网格中取一个 N×1 的矩形，并把它当作一个无向图。这个图有 2(N+1) 个顶点，有 3(N-1)+4 条边。这个图有多少个生成树？
样例输入
1
样例输出
4
（数据范围、时空限制、输入输出格式同上）
问题分析
（为了方便起见，在这里的分析中，我假设矩形从下到上安排） 首先我们可以定义 表示高度为 的矩形形成生成树的个数。最开始我想到一个 naive 的想法：最底下的一个矩形有四种情况，上面每增加一个就有三种情况（如图），所以答案就是 ！
但是现实很残酷，很显然“梯子形”没有被我考虑到，即这样的情况：
所以我们不得不换一种定义： 表示有 个正方形，其中最上面一个正方形的最上面一条边取了/没取。因为接下来加入的正方形只和最上面一条边有关。考虑状态转移：
-
先考虑 如何转移：很简单，新加入的正方形上面一条边不取，只有一种情况，即“| |”。
-
接下来看看 怎么转移。
-
如果下面矩形最上面一条边没取，则有两种情况：左上、右上。
-
如果下面矩形最上面一条边取了，那么我们还要再考虑一种情况：可以把这条边拿来当做加入的正方形的最上面一条边（这个真的是想不到）。这样才保证了上面所述的“梯子形”可以考虑到。
转移方程：
代码
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1005,tt=12345;
int n,f[maxn][2];
int main(){
scanf("%d",&n);
f[1][0]=3;f[1][1]=1;
for (int i=2;i<=n;i++){
f[i][0]=(f[i-1][1]*2%tt+f[i-1][0]*3%tt)%tt;
f[i][1]=(f[i-1][0]+f[i-1][1])%tt;
}
printf("%d\n",(f[n][0]+f[n][1])%tt);
return 0;
}