P8680 [蓝桥杯 2019 省 B] 特别数的和

题目描述

如果一个数的十进制表示法中，任何相邻的两个数字均不相同，那么这个数就被称为 “有趣的数”。例如，以下各数都是有趣的数：

1、21、321、4321

但是，以下各数却不是有趣的数：

22、121、3212

给出正整数 n，请你求出长度为 n 的有趣的数的个数，并输出这个值除以 998244353 的余数。

输入格式

输入一行，包含一个整数 n。

输出格式

输出一个整数，表示答案除以 998244353 的余数。

数据范围

1≤n≤1000

输入样例1：

2

输出样例1：

81

输入样例2：

3

输出样例2：

531441

题解

有趣的数
求长度为n的有趣数的个数

思路：

第一位有9种选择，第二位有9种选择，第三位有8种选择（因为只有和前一位不一样才可以）

代码1：

时间复杂度 O(n)

C++ 代码

#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
int n;
scanf("%d", &n);

int mod = 998244353;

long long res = 1;
for (int i = 1; i <= n; i ++ )
res = res * (i <= 2 ? 9 : 10 - i % 2) % mod;

printf("%lld\n", res);

return 0;
}

代码2：

时间复杂度 O(n)

C++ 代码

#include <iostream>
#include <cstdio>

using namespace std;

const int MOD = 998244353;

int main()
{
int n;
scanf("%d", &n);

int f[1010][10];
for (int i = 0; i < 10; i ++ ) f[1][i] = 1;

for (int i = 2; i <= n; i ++ )
for (int j = 0; j < 10; j ++ )
for (int k = 0; k < 10; k ++ )
if (j != k)
f[i][j] = (f[i][j] + f[i - 1][k]) % MOD;

int res = 0;
for (int i = 1; i < 10; i ++ ) res = (res + f[n][i]) % MOD;

printf("%d\n", res);

return 0;
}