CodeRookie

用户名：Shmily124

访问量：133706

签　名：

清风前烹茶对弈，明月下把酒言欢

等　　级
排　　名	14
经　　验	22985
参赛次数	7
文章发表	39
年　　龄	0
在职情况	学生
学　　校	ZUA
专　　业	计科

　　自我简介：

悄悄地秃头，然后惊艳所有人？

TA的其他文章

蓝桥杯2022年第十三届省赛真题-李白打酒加强版（记忆化搜索+剪枝）C++
浏览：1503

1105: 数列数组模拟与位运算 C/C++
浏览：416

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(1) （C++代码）

1105: 数列数组模拟与位运算 C/C++

　　作者: CodeRookie　　　　发表时间：2022-05-09 23:33:31 浏览：416　|　评论：0　

原题链接：数列

### 模拟

看到 n 最大为 1000，那么暴力模拟也无所谓，复杂度也只不过 O(n)而已

定义一个数组

**每轮循环先在数组尾部加入新的指数幂**

**然后拿这个幂与此前的每一个数相加依次添加至数组尾部**

最终 arr[n - 1] 就是所求的答案

```cpp
#include <cstdio>

int k, n, sz = 0;	// sz表示当前数组里有效的数字个数 
int a[1005];

int main() {
	scanf("%d %d", &k, &n);
	for (int bac = 1; sz < n; bac *= k) {	// bac表示幂运算结果
		int m = sz;		//先记下当前有效个数 
		a[sz++] = bac;	//将新的幂运算加入尾部 
		for (int i = 0; i < m && sz < n; i++) {		//将新的幂与之前的结果相加 
			a[sz++] = a[i] + bac;
		}
	}
	printf("%d\n", a[n - 1]);
	return 0;
}
```

### 位运算

将 n 转化为 2 进制，可以发现

2 进制从右往左的第 i 位 ( i 从 0 开始) 对应着是否包含 k 的 i 次方

如下：

0001    对应    p^0

0010    对应    p^1

0011    对应    p^1 + p^0

0100    对应    p^2

……

**对 n 不断循环右移，每次循环判断最右一位是否为1**

**同时计算每一位对应幂运算的结果**

**若 (n & 1) == 1 则加上幂结果**

**直到 n 变为 0 停止**

时间复杂度 O(log(n))

```cpp
#include <cstdio>

int k, n; 
int main() {
	scanf("%d %d", &k, &n);
	int ans = 0, bac = 1;	//此处类型改为 long long 无法通过
	while (n) {
		if (n & 1) ans += bac;
		bac *= k;
		n >>= 1;
	}
	printf("%d\n", ans);	// 若用 long long 应改为 lld 占位符
	return 0;
}
```

题面上说：**（在所有的测试数据中，结果均不超过2.1*109）**

是在暗示结果不会超过 int 类型上限 ( int 类型最大为  2147483648 )

**然而这句话是骗人的……**

因为用 long long 来计算结果会无法通过最后一个样例

而 int 却可以，奇怪了，怎么会有 long long 过不了而 int 能过的答案

所以，**测试数据可能把 int 类型溢出后的结果当作了正确答案**

0.0分

4 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

CodeRookie

TA的其他文章

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(1) （C++代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

一个简单易懂的代码

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

1105: 数列数组模拟与位运算 C/C++

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言训练-大、小写问题（C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

WU-小九九（C++代码）

剪刀石头布（C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

关于float，double变量的几点说明

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

A+B for Input-Output Practice (I) （C语言代码）

CodeRookie

TA的其他文章

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(1) （C++代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

一个简单易懂的代码

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

1105: 数列 数组模拟与位运算 C/C++

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言训练-大、小写问题 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）

WU-小九九 （C++代码）

剪刀石头布 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

关于float，double变量的几点说明

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

A+B for Input-Output Practice (I) （C语言代码）

1105: 数列数组模拟与位运算 C/C++

　　评论区

C语言训练-大、小写问题（C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

WU-小九九（C++代码）

剪刀石头布（C语言代码）