「CometOJ3842」计算器(computer)

题意：小 $X$ 有一台奇怪的计算机。这台计算机首先会读入一个正整数 $n$($1\le n\le 10^{18}$)，然后生成一个包含 $n$ 个数的序列 $a$。一开始 $a_i(1 \le i \le n)$ 的值均为 $1$。接下来，小 X 会进行 $n-1$ 次操作，每次操作会输入一个指令，这个指令有 $2$ 种情况：

1. x + 表示把此时序列中第 $x$ 个数 $a_x$ 和第 $x+1$ 个数 $a_{x+1}$ 合并为一个数，值为 $a_x + a_{x+1}$。
2. x * 表示把此时序列中第 $x$ 个数 $a_x$ 和第 $x+1$ 个数 $a_{x+1}$ 合并为一个数，值为 $a_x \times a_{x+1}$。

假设某个时刻序列中元素的个数为 $k$，小 X 必须保证 $1 \le x < k$。那么，经过 $n-1$ 次操作后，序列只剩下了一个数，此时计算机会输出这个数。小 X 想知道，当他输入 $n$ 时，这台计算器输出的数最大会是多少。由于这个数可能会很大，你只需要求出这个数模 $10^9+7$ 的值。

模拟大法好！！

首先看到 $n$ 这么大的范围，那么几乎只有 $O(1)$ 或 $O(\log)$ 算法了。

我们易知，当 $n\le 4$ 时，答案就是 $n$。

当 $n>4$ 时，这里有一个简单的定理：

先做加法再做乘法一定比先做乘法在做加法更优。

证明：$\forall a,b,c$，其中 $a\ge 1$，必然有 $(a\times b)+c\leq a\times(b+c)$，两者相差 $(a-1)\times c$。

所以题意可以转化为：将序列拆成若干个正整数的和，最大化其乘积。

容易发现，当拆分的数中，如果有一个数 $a\ge 4$，那么 $2\times (a-2)$ 不会更差。

又因为不会拆分出 $1$ (无意义)，所以拆成的数只有 $2$ 和 $3$。

$2$ 和 $3$ 的最小公倍数为 $6$，所以每 $6$ 个数，拆成 $3$ 个 $2$ 和拆成 $2$ 个 $3$ 的花费相同。

又因为 $2 ^3 = 8 < 9 =3 ^2$，所以都拆成 $3$ 一定更优。

那么对于 $n\ge 4$，我们开始分情况讨论：

1. 如果 $n\equiv 0\bmod 3$，那么答案为 $3^{\frac{n}{3}}$；

2. 如果 $n\equiv 1\bmod\ 3$，那么可以拆分成为 $1\times 3^{\frac{n-1}{3}}$ 和 $4\times 3^{\frac{n-4}{3}}$，很明显前式 $<$ 后式(拆分出 $1$ 肯定不优)，所以答案为 $4\times 3^{\frac{n-4}{3}}$；

3. 如果 $n\equiv 2\bmod 3$，那么答案为 $2\times 3^{\frac{n-2}{3}}$。

随后快速幂直接解决(注意开 long long)。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
long long n,mod=1e9+7;
long long power(long long a,long long b,long long p)
{
	long long ans=1%p;
	for(;b;b>>=1)
	{
		if(b&1)
			ans=ans*a%p;
		a=a*a%p;
	}
	return ans%p;
}
int main()
{
	scanf("%lld",&n);
	if(n<=4)
		printf("%lld\n",n);
	else
	{
		if(n%3==0)
			printf("%lld",power(3,n/3,mod));
		else if(n%3==1)
			printf("%lld",4%mod*power(3,(n-4)/3,mod)%mod);
		else
			printf("%lld",2%mod*power(3,(n-2)/3,mod)%mod);
	}
	return 0;
}