题解 P6195 【[EER1]迫害】

· · 题解

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

【目录】

【写在前面】

本题解的代码关系是递进的，每一次的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