递推专项训练五题题解

今天的 XY 题居然是递推专题，五道题目全都是递推，30+个人 AK 了……

递推是按照一定的规律来计算序列中的每个项，通常是通过计算前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。

"利用了计算机速度快和不知疲倦的机器特点" :no_mouth:

蛇皮目录

问题一

题目描述

在所有的 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)$ 的状态转移。转移方程：

代码

#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$ 行的方案数，那么递推式很容易得出：

代码

#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 步，最后一步向上/左/右走的方案数。那么上次是向右边走，这次就不能向左边走；上次向左，这次就不能向右。这样就可以直接进行状态转移了：

代码

#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)$

• 与某个点连接，可以看成连成的这条边把点集分成了两部分，左右两部分剩下的点分别连边，方案数分别相乘。

在上述手算过程中我们发现了规律，总结出递推式就是：

代码

#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)$ 怎么转移。

• 如果下面矩形最上面一条边没取，则有两种情况：左上、右上。

• 如果下面矩形最上面一条边取了，那么我们还要再考虑一种情况：可以把这条边拿来当做加入的正方形的最上面一条边（这个真的是想不到）。这样才保证了上面所述的“梯子形”可以考虑到。

转移方程：

代码

#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;
}