2015 HDU 多校联赛 5363 Key Set
题目: http://acm.hdu.edu.cn/showproblem.php?pid=5363
依据前面给出的样例，得出求解公式 fn = 2^(n-1) - 1, 数据量大，实际就是求幂次方。
可用分治法求解。复杂度O(nlogn)
// 分治法求高速幂
#include
using namespace std;
typedef unsigned long long ull;
const int MOD = 1000000007;
ull getAns(ull a, int n)
{
if (n==0)
return 1;
if (n==1)
return a;
else
{
a %= MOD;
ull res = a*a;
res %= MOD;
if (n%2 == 0)
{
return getAns(res, n/2)%MOD;
}
else
{
return (getAns(res, n/2)*a)%MOD;
}
}
}
int main(void)
{
//freopen("in.txt", "r", stdin);
int t = 0;
scanf("%d", &t);
ull a = 2;
while(t--)
{
int n = 0;
scanf("%d", &n);
printf("%lld\n", getAns(a, n-1)-1); // 2^(n-1) - 1
}
return 0;
}
发表评论