# 剑指 Offer 16. 数值的整数次方

输入: 2.00000, 10



输入: 2.10000, 3



输入: 2.00000, -2

• -100.0 < x < 100.0
• n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

class Solution {
public:
double myPow(double x, int n) {

long long m = n;
if(m < 0) m = -m;

double ans = 1.0;
while(m != 0) {
if(m % 2 == 1) {
ans *= x;
}
x *= x;
m >>= 1;
}
if(n < 0) return 1.0 / ans;
else return ans;
}
};

# 剑指 Offer 14- II. 剪绳子 II

输入: 2

输入: 10

• 2 <= n <= 1000

typedef long long LL;

class Solution {
private:
LL FastPow(LL x, LL y) {
LL ans = 1;
while(y != 0) {
if(y % 2 == 1) {
ans = ans * x % 1000000007;
}
x = x * x % 1000000007;
y >>= 1;
}
return ans % 1000000007;
}
public:
int cuttingRope(int n) {
if(n <= 3) return n - 1;
int m = n / 3;
if(n % 3 == 0) {
return FastPow(3, m) % 1000000007;
} else if(n % 3 == 1) {
return (FastPow(3, m - 1) % 1000000007) * 4 % 1000000007;
} else {
return (FastPow(3, m) % 1000000007) * 2 % 1000000007;
}
}
};

# 剑指 Offer 10- I. 斐波那契数列

F(0) = 0,   F(1) = 1
F(N) = F(N – 1) + F(N – 2), 其中 N > 1.

0 <= n <= 100

class Solution {
public:
int fib(int n) {
if(n == 0) return 0;
if(n == 1) return 1;
long long a = 0, b = 1;
for(int i = 2; i <= n; ++i) {
long long tmp = a + b;
tmp %= 1000000007;
a = b;
b = tmp;
}
return b;
}
};

typedef long long LL;

class Solution {
private:
vector<vector<LL>> multiply(vector<vector<LL>> &m1, vector<vector<LL>> &m2) {
int n = m1.size();
vector<vector<LL>> ans(n, vector<LL>(n, 0));
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
for(int k = 0; k < n; ++k) {
ans[i][j] += m1[i][k] * m2[k][j] % 1000000007;
}
}
}
return ans;
}
public:
int fib(int n) {
if(n == 0) return 0;
if(n == 1) return 1;

vector<vector<LL>> matrix = {{1,1},{1,0}};

vector<vector<LL>> ans = {{1,0},{0,1}};
while(n != 0) {
if(n % 2 == 1) ans = multiply(ans, matrix);
matrix = multiply(matrix, matrix);
n >>= 1;
}

return ans[0][1] % 1000000007;
}
};

# LeetCode Super Pow

LeetCode Super Pow Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array. Example1:

a = 2
b = [3]
Result: 8

Example2:
a = 2
b = [1,0]
Result: 1024

# hihoCoder 1504-骑士游历

hihoCoder 1504-骑士游历

### 输出

2 1 1

12

# LeetCode Pow(x, n)

50. Pow(x, n)

Implement pow(xn), which calculates x raised to the power n (xn).

Example 1:

Input: 2.00000, 10
Output: 1024.00000


Example 2:

Input: 2.10000, 3
Output: 9.26100


Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25


Note:

• -100.0 < x < 100.0
• n is a 32-bit signed integer, within the range [−231, 231 − 1]

class Solution {
public:
double doPow(double x, int n)
{
if (n == 0)
return 1.0;
double v = doPow(x, n / 2);
if (n % 2 == 0)
return v * v;
else
return v * v * x;
}
double myPow(double x, int n)
{
int m = n > 0 ? n : -n;
double ans = doPow(x, m);
return n > 0 ? ans : 1.0 / ans;
}
};

class Solution {
public:
double myPow(double x, int n)
{
if (n == 0)
return 1;
if (n == 1)
return x;
long long m = n; // 先转换为ll，否则n=INT_MIN是有问题
m = m > 0 ? m : -m;
double ans = 1;
while (m) {
if (m & 1)
ans *= x;
m >>= 1;
x = x * x;
}
return n > 0 ? ans : 1 / ans;
}
};

class Solution {
public:
double myPow2(double x, long long m) {
if (x == 0.0)return 0.0;
if (x == 1.0 || m == 0)return 1.0;
if (m == 1)return x;
if (m < 0) return 1.0 / myPow2(x, -m);

if (m % 2 == 1)return x * myPow2(x*x, m >> 1);
else return myPow2(x*x, m >> 1);
}
double myPow(double x, int n) {
return myPow2(x, n);
}
};

# HDOJ 5392-Infoplane in Tina Town

HDOJ 5392-Infoplane in Tina Town Infoplane in Tina Town Time Limit: 14000/7000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others) Total Submission(s): 1636 Accepted Submission(s): 385 Problem Description There is a big stone with smooth surface in Tina Town. When people go towards it, the stone surface will be lighted and show its usage. This stone was a legacy and also the center of Tina Town’s calculation and control system. also, it can display events in Tina Town and contents that pedestrians are interested in, and it can be used as public computer. It makes people’s life more convenient (especially for who forget to take a device). Tina and Town were playing a game on this stone. First, a permutation of numbers from 1 to n were displayed on the stone. Town exchanged some numbers randomly and Town recorded this process by macros. Town asked Tine,”Do you know how many times it need to turn these numbers into the original permutation by executing this macro? Tina didn’t know the answer so she asked you to find out the answer for her. Since the answer may be very large, you only need to output the answer modulo 3∗230+1=3221225473 (a prime). Input The first line is an integer T representing the number of test cases. T≤5 For each test case, the first line is an integer n representing the length of permutation. n≤3∗106 The second line contains n integers representing a permutation A1…An. It is guaranteed that numbers are different each other and all Ai satisfies ( 1≤Ai≤n ). Output For each test case, print a number ans representing the answer. Sample Input 2 3 1 3 2 6 2 3 4 5 6 1 Sample Output 2 6 Source BestCoder Round #51 (div.2) Recommend hujie | We have carefully selected several similar problems for you: 5395 5394 5393 5390 5389