/ Vijos / 题库 /

河蟹的字串复制

河蟹的字串复制

描述

河蟹是一个打字员,他经常要重复将某个字串复制很多遍。但他又很笨,每次打完初始字串后都只会按Ctrl+A、Ctrl+C,再按N下Ctrl+V将其复制到N遍(使屏幕上出现N个初始字串),于是经常弄得他满头是汗。为了减轻他的工作量,他委托你编写一个程序,求:从一个初始字串开始,按住Ctrl不放,最少要按多少个键(A或C或V)才能将字串复制到N遍呢?并且请你算出在按键最少的情况下有多少种不同按法。

格式

输入格式

只有一行,即数N。

输出格式

包含两行,第一行是最少按键数,第二行是不同的按法总数。

样例1

样例输入1

15

样例输出1

12
2

限制

因数据点而不同,最多5s,最少1s。

提示

[样例解释]
两种按法可以得到15个初始字串:
Ctrl+A+C+V+V+V+A+C+V+V+V+V+V
Ctrl+A+C+V+V+V+V+V+A+C+V+V+V
[题目提示]
沙茶题,别想繁了!!!
[数据规模]
对于20%的数据,N<=10000(即ZeroJudge原题数据范围)
对于50%的数据,N<=10^8
对于100%的数据,2<=N<=10^16

来源

ZeroJudge d304,有较大改动,组合键的功能更接近真实,数据范围也扩大了很多。当然,由于数据范围扩大了,也就不能输出方案了。

信息

ID
1606
难度
9
分类
贪心 | 高精度 点击显示
标签
(无)
递交数
333
已通过
12
通过率
4%
上传者

相关

在下列训练计划中:

RP++分类题库