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