自动搬运

查看原文

来自洛谷，原作者为

	MZY666 「It's time to see what I can do_To test the limits and break through.」

搬运于2025-08-24 22:18:26，当前版本为作者最后更新于2020-03-11 07:36:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

原题传送门。在我的博客中食用更佳。

【目录】

• 目录
• 写在前面
• 题意概括
• 思路
• 激动人心的代码实现环节
• 尾声

【写在前面】

本题解的代码关系是递进的，每一次的Code无不是包含着作者的菜与艰辛。

如果有意见欢迎提出，但请私信（作者自愿禁言了），否则作者无法回复您。

【题意概括】

输入两个正整数 $n$，$m$ 。

其中 $n$ 表示你拥有 $n$ 张值为 $1$ 的卡片 $A$，$m$ 则表示你拥有 $m$ 张可以自定义为任何值的卡片 $B$（定义后不可更改）。

现要求用这些卡片从 $1$ 开始一个一个地表示下一个数（包括 $1$），直到无法表示为止，求最大能表示到的值。

注意结果要对 $10^9+7$ 取余。

【思路】

或许你从样例身上已经有了一些想法了：先将所有卡片 $A$ 用完，这些卡片可以表示从 $1$ 到 $n$ 的所有整数。

随后下一个数 $n+1$ 又该如何表示呢？别忘了，我们还有可以自行定义值的卡片。

那么，不妨令第一张卡片 $B$ 的值为 $n+1$。这样就可以先解决表示 $n+1$ 的问题。

随后，$n+2$ 就可以表示为 $(n+1)+(1)$。此处的括号是用来区分两种卡片的。

同理：

$$n+3=(n+1)+(2)$$ $$n+5=(n+1)+(4)$$ $$......$$ $$n+n+1=(n+1)+(n)$$

我们就会发现，此时能表示到的最大的值就是 $2n+1$ 了。

那么此时：

如果我们没有卡片 $B$ 了，那么能表示到的最大的值就是 $2n+1$，结束。

如果还有，那就可以令下一张卡片 $B$ 的值为 $2n+2$ ，随后重复以上步骤。

发现当有两张卡片 $B$ 时能表示到的最大的值就是 $4n+3$。

咱们先停一停，找找规律：

当有 $1$ 张卡片 $B$ 时，所能表示到的最大的值是 $2n+1$。

当有 $2$ 张卡片 $B$ 时，所能表示到的最大的值是 $4n+3$。

由上可得，当有 $m$ 张卡片 $B$ 时，所能表示到的最大的值是 $2^m \times (n+1)-1$。

如果你觉得两次得来的规律不可靠，也可以再看看有 $3、4$ 张卡片 $B$ 时各所对应的最大值是多少，再看看符不符合刚刚找到的规律。最后你会发现这是对的。

那么，是时候进入下一章节了，我想你应该已经迫不及待了吧...

【激动人心的代码实现环节】

好了，咱先不管那么多，先按刚刚得到的还热乎着的规律打一发再说：

First Code:

#include<bits/stdc++.h>//万能头文件好
using namespace std;
#define ll long long//个人习惯
#define mo 1000000007
int main(){
	ll n,m;
	scanf("%lld%lld",&n,&m);//输入
	printf("%lld\n",(n+1)* ( (ll) (pow(2,m)) ) %mo-1);//输出
	//没错，就是这么简单！
  	return 0;//over!
}

看啊，那一个个绿色的AC是那么的可爱！

往下一翻：Emm怎么全错了。。

聪明的你一定发现了：我并没有给最后答案取余。那么简单再改一下：结果Q_Q。

不急，问题不大，至少没有TLE，况且比赛才开始呢。仔细想想...中间乘的时候是不是爆long long了？没错！就是这样！

那么我们就可以把算 $2^m$ 的步骤单独拿出来算，每乘一次2就膜一次 $10^9+7$。

Second Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mo 1000000007
int main(){
	ll n,m,k=1,i;//注意k的初始值
	scanf("%lld%lld",&n,&m);
	for(i=1;i<=m;i++)k*=2,k%=mo;//用k来存储2^m的结果
	printf("%lld\n",((n+1)*(k%mo)-1)%mo);
  	return 0;
}

很好，看来可以A掉了。成功解锁此题新死法：TLE。

看来，T3说的真好：

个人的遭遇，命运的多舛都使我被迫成熟，这一切的代价都当是日后活下去的力量。 —— 三毛

咱们打起精神再来。既然TLE是时间不够，那么就得让程序算 $2^m$ 时快一点。可我又不会快速幂咋办呢。

办法总比困难多。我们可以让循环变快一些。

若用一个变量 $yu$ 来存储 $m$ 对 $3$ 取余的结果，再让 $m$ 自身整除以 $3$，则：

$$k=({2^3})^m \times 2^{yu}$$

上Third Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mo 1000000007
int main(){
	ll n,m,k=1,i,yu;//先全部定义好
	scanf("%lld%lld",&n,&m);
	yu=m%3;m/=3;//取余，自整除
	for(i=1;i<=m;i++)k*=8,k%=mo;//算(2^3)^m
	for(i=1;i<=yu;i++)k*=2,k%=mo;//算2^yu
	printf("%lld\n",((n+1)*(k%mo)-1)%mo);
  	return 0;
}

再次喜提TLE。

嘿，别泄气啊，你看，TLE的点数不是少了几个？

程序能不能再快一点？

当然可以！为什么不让循环跨度再大一点呢？也就是使：

$$k=({2^5})^m \times 2^{yu}$$

这次就不上Forth Code了，与Third Code是同理的。

结果：AC哈哈哈！

【尾声】

然而窝太篛了只A了 $T1$，$T2$。

众所周知，月赛排名是先按分数，再按时间排序的。

百般无奈的我为了更上一层楼便开始琢磨...

能不能再快点？

当然可以！为什么不让循环跨度再大一点呢？（我绝对不会告诉你们这句话是从前面复制过来的）

于是，我让 $m$ 对 $15$ 取了余。似乎已经跑的很快了（毕竟不是正解），11ms（也不知它是怎么算的） 美滋滋~

还是上一下上述的Forth Code吧：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mo 1000000007
int main(){
	ll n,m,k=1,i,yu;
	scanf("%lld%lld",&n,&m);
	yu=m%15;m/=15;
	for(i=1;i<=m;i++)k*=32768,k%=mo;//如果我说32768是我口算的，你信吗？
	for(i=1;i<=yu;i++)k*=2,k%=mo;
	printf("%lld\n",((n+1)*(k%mo)-1)%mo);
  	return 0;
}

跑的挺快的记录。

顺便说一下，其实这道题作者有Sixteenth Code（好丢脸）。

码字不易啊（疯狂暗示 AWA