2015 HDU 多校联赛 5363 Key Set

题目:?pid=5363

根据前面给出的例子，得出求解公式 fn = 2^(n-1) – 1, 数据量大，实际就是求幂次方。

可用分治法求解，复杂度O(nlogn)

// 分治法求快速幂#include <bits/stdc++.h>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;}

，与其临渊羡鱼，不如退而结网。

相关文章：

你感兴趣的文章：

标签云：