今天的 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)$:

同理可以得出 $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

(数据范围、时空限制、输入输出格式同上)

问题分析

也是很显然的递推题……一般这种题目我们可以“找规律”:

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

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