Tag Archives: 快速幂

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

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

实现函数double Power(double base, int exponent),求base的exponent次方。不得使用库函数,同时不需要考虑大数问题。

示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.10000, 3
输出: 9.26100

示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

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

注意:本题与主站 50 题相同:https://leetcode-cn.com/problems/powx-n/


实现函数pow(x,n),与LeetCode Pow(x, n)相同,快速幂。完整代码如下:

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;
    }
};

本代码提交AC,用时0MS。

剑指 Offer 14- II. 剪绳子 II

剑指 Offer 14- II. 剪绳子 II

给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示:

  • 2 <= n <= 1000

注意:本题与主站 343 题相同:https://leetcode-cn.com/problems/integer-break/


本题是上一题(剑指 Offer 14- I. 剪绳子 LCOF)的升级版,即n的范围变大了,导致次方超过int和long long的范围,需要在求pow的过程中取mod。使用快速幂的方法,代码如下:

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;
        }
    }
};

本代码提交AC,用时0MS。

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

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

写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项。斐波那契数列的定义如下:

F(0) = 0,   F(1) = 1
F(N) = F(N – 1) + F(N – 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 2
输出:1
示例 2:

输入:n = 5
输出:5
 

提示:

0 <= n <= 100
注意:本题与主站 509 题相同:https://leetcode-cn.com/problems/fibonacci-number/

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


求斐波那契数列的第n项。看之前的POJ题解: http://code.bitjoy.net/2017/05/04/poj-3070-fibonacci/

一共有三种解法。常规解法就是无脑递归调用。关键是如何分析这种解法的时空复杂度。无脑调用是F(n)=F(n-1)+F(n-2)。想象一下,递归调用二叉树( https://wmjtxt.github.io/2018/12/26/three_method_of_fibonacci/ )。每个节点都会分裂出2个孩子,然后孩子继续2倍分裂,所以总调用次数大概是$O(2^n)$,这是时间复杂度。空间复杂度就是递归调用的栈深度,就是树的高度,大概是$O(n)$。

常规解法是,DP的思路,每次保留数列前两项,然后不断更新这两个数。时间复杂度是$O(n)$,空间复杂度是O(1)。完整代码如下:

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;
    }
};

本代码提交AC,用时0MS。

最优的解法是矩阵快速幂的方法,求矩阵[[1,1],[1,0]]的n次幂,然后矩阵逆对角线位置的值就是F(n)的值。快速幂可以做到$O(lg(n))$的时间复杂度,完整代码如下:

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;
    }
};

本代码提交AC,用时4MS。

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

快速幂的进阶版,超级幂。要求$$a^B=a^{[b_0,b_1,b_2,…b_{n-1}]}$$,其中的B用一个数组来表示,数组中的元素都是个位数,分别从高位到低位。比如第二个样例表示的是$$2^10$$。 我一开始把$$a^B=a^{[b_0,b_1,b_2,…b_{n-1}]}$$展开成$$a^B=a^{b_0*10^{n-1}+b_1*10^{n-2}+…}$$,对于每一项都用快速幂算出$$10^{n-i-1}$$,然后用快速幂算出$$a^{b_i*10^{n-i-1}}$$,最后累乘起来。但是很不幸WA或者TLE。 后来看了网上的题解,发现真是巧妙,这不就类似于多项式计算时层层嵌套的方法吗,一时想不起来那个叫什么名字了。比如我们要算$$a^{[b_0,b_1,b_2]}$$,本来是$$a^{b_0*10^2+b_1*10+b_2}$$。但是我们计算是可以这样算,先算$$C_0=a^{b_0}$$;递归到$$b_1$$时,在算到$$b_0$$的基础上,有$$C_1=(a^{b_0})^{10}*a^{b_1}=C_0^{10}*a^{b_1}$$;递归到$$b_2$$时,有$$C_2=((a^{b_0})^{10}*a^{b_1})^{10}*a^{b_2}=C_1^{10}*a^{b_2}$$。把$$C_2$$展开其实就是$$a^{b_0*10^2+b_1*10+b_2}$$。 完整代码如下: [cpp] typedef unsigned long long ull; class Solution { private: const static int MOD = 1337; ull fastPow(ull x, ull y) { ull ans = 1; while (y) { if (y & 1)ans = (ans*x) % MOD; y >>= 1; x = (x*x) % MOD; } return ans; } public: int superPow(int a, vector<int>& b) { ull ans = 1; for (int i = 0; i < b.size(); ++i) { ans = fastPow(ans, 10)*fastPow(a, b[i]) % MOD; } return ans; } }; [/cpp] 本代码提交AC,用时9MS。]]>

hihoCoder 1504-骑士游历

hihoCoder 1504-骑士游历

#1504 : 骑士游历

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

在8×8的国际象棋棋盘上给定一只骑士(俗称“马”)棋子的位置(R, C),小Hi想知道从(R, C)开始移动N步一共有多少种不同的走法。

输入

第一行包含三个整数,N,R和C。 对于40%的数据, 1 <= N <= 1000000 对于100%的数据, 1 <= N <= 1000000000 1 <= R, C <= 8

输出

从(R, C)开始走N步有多少种不同的走法。由于答案可能非常大,你只需要输出答案模1000000007的余数。
样例输入
2 1 1
样例输出
12

在国际象棋上,给定马的起点(R,C),问走N步共有多少种走法。 这题我最开始是用DFS做的,但是只能过一部分数据,对于100%的数据,N最大居然可以达到1000000000,太恐怖了。 后来问了大神,说是用矩阵快速幂来做,恍然大悟。 在我介绍的马尔可夫聚类算法博客中,初始时给定一个图的邻接矩阵A,则$$B=A^n$$中B[i][j]表示从i点到j点走n步的方案数。MCL算法为了满足随机游走,还加上了单位矩阵,具体的例子可以看我那篇博客的图。 这个题就是用MCL的方法来做的。国际象棋的棋盘是8*8的,也就是有64个位置,初始时我们可以算到每个点走一步能走到的位置,这样就能得到一个64*64的邻接矩阵A。然后使用快速幂计算$$B=A^n$$。最后把起始点(R,C)转换为一个1*64的行向量,左乘B矩阵,得到一个1*64的行向量。这样做的含义就是从(R,C)出发,走n步到达每个点的方案数。把结果行向量的元素累加起来就是总的方案数。 完整代码如下,最后一步时,直接取出幂矩阵的第idx行即可,没必要再构造一个只含一个元素的矩阵,再左乘了。 [cpp] #include<iostream> #include<vector> using namespace std; typedef long long LL; vector<vector<int>> dirs = { { 1,2 },{ 1,-2 },{ 2,1 },{ 2,-1 },{ -2,1 },{ -2,-1 },{ -1,2 },{ -1,-2 } }; const int MAXN = 8; const LL MOD = 1000000007; vector<vector<LL>> matrix(MAXN*MAXN, vector<LL>(MAXN*MAXN, 0)); inline bool ok(const int &x, const int &y) { return x >= 0 && x < MAXN && y >= 0 && y < MAXN; } inline int id(const int &x, const int &y) { return x*MAXN + y; } void init() { for (int i = 0; i < MAXN; ++i) { for (int j = 0; j < MAXN; ++j) { for (int k = 0; k < dirs.size(); ++k) { int x = i + dirs[k][0], y = j + dirs[k][1]; if (ok(x, y))matrix[id(i, j)][id(x, y)] = 1; } } } } vector<vector<LL>> multi(const vector<vector<LL>>& mat1, const vector<vector<LL>>& mat2) { vector<vector<LL>> ans(MAXN*MAXN, vector<LL>(MAXN*MAXN, 0)); for (int i = 0; i < MAXN*MAXN; ++i) { for (int j = 0; j < MAXN*MAXN; ++j) { for (int k = 0; k < MAXN*MAXN; ++k) { ans[i][j] = (ans[i][j] + mat1[i][k] * mat2[k][j]) % MOD; } } } return ans; } vector<vector<LL>> pow(vector<vector<LL>>& mat, int n) { vector<vector<LL>> ans(MAXN*MAXN, vector<LL>(MAXN*MAXN, 0)); for (int i = 0; i < MAXN*MAXN; ++i)ans[i][i] = 1; // 单位阵 while (n != 0) { if (n & 1)ans = multi(ans, mat); mat = multi(mat, mat); n >>= 1; } return ans; } int main() { int n, r, c; scanf("%d %d %d", &n, &r, &c); –r; –c; init(); vector<vector<LL>> finalMat = pow(matrix, n); int idx = id(r, c); // first way: long long ans = 0; for (int i = 0; i < MAXN*MAXN; ++i)ans = (ans + finalMat[idx][i]) % MOD; printf("%lld\n", ans); // second way: //vector<vector<LL>> one(MAXN*MAXN, vector<LL>(MAXN*MAXN, 0)); //one[idx][idx] = 1; //one = multi(one, finalMat); //long long ans = 0; //for (int i = 0; i < MAXN*MAXN; ++i) { // for (int j = 0; j < MAXN*MAXN; ++j) { // ans = (ans + one[i][j]) % MOD; // } //} //printf("%lld\n", ans); return 0; } [/cpp] 本代码提交AC,用时412MS。]]>

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]

实现幂指数运算。 如果对x连乘n次,时间复杂度为$O(n)$,但使用分治法能降到$O(\log n)$。因为可以把$x^n$分解为: $\begin{equation*} x^n= \begin{cases} x^{\frac{n}{2}} \cdot x^{\frac{n}{2}}, & \text{if } n \text{ even}\\ x^{\frac{n-1}{2}} \cdot x^{\frac{n-1}{2}} \cdot x, & \text{if } n \text{ odd} \end{cases} \end{equation*}$

完整代码如下:

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;
    }
};

本代码提交AC,用时3MS。
注意在子程序中不要调用两次doPow(x, n/2),算出一个v,然后直接v*v即可。

二刷。使用非递归的方法实现快速幂,代码如下:

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;
    }
};

本代码提交AC,用时3MS。

三刷。注意n=INT_MIN时,第一种解法会有问题,需要用long long存储,代码如下:

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);
	}
};

本代码提交AC,用时0MS。

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


此题和POJ 2369-Permutations类似,只是测试样例更多,数据规模更大,最后还要对某个大数取模。所以在求所有循环节长度的最小公倍数的时候,不能使用gcd转换的方法,需要先后使用因式分解和快速幂算法。 参考下面的例子理解分解质因数法求最小公倍数的方法。 60=2×2×3×5 18=2×3×3 lcm(60,18)=180=2×2×3×3×5 通过观察可以看出规律,要求a,b的最小公倍数,先将a和b分解成质因数相乘的形式,对于每一个质因子x,取x在a和b中出现频率最高的数作为x在最小公倍数中的频率。比如2在60中出现2次,但在18中只出现1次,所以2在最小公倍数180中也出现2次,同理质因子3和5分别出现2次和1次。 假设某个质因子x出现y次,则最后要计算$$x^ymodp$$,可以使用快速幂方法提高速度,该方法很好理解,将y看成二进制形式,如果y为偶数,则$$x^y=(x*x)^{y/2}$$;如果y为奇数,则$$x^y=x*x^{y-1}$$,y-1就是偶数了。同时modp就是快速幂取模了。 完整代码如下: [cpp] #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef unsigned long long ULL; const int kMaxN = 3000005, kNumPrime = 269; const ULL kMod = 3221225473; bool visited[kMaxN]; int permutation[kMaxN]; int prime[kNumPrime] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723 }; int prime_times[kMaxN]; //求x的所有质因子及其频率 void GetPrimeFactor(int x) { for (int i = 0; i < kNumPrime; i++) { int tmp = 0; while (x%prime[i] == 0) { tmp++; x /= prime[i]; } if (tmp > prime_times[prime[i]]) prime_times[prime[i]] = tmp; if (x == 1) return; } prime_times[x]++; } //快速幂取模x^ymod(kMod) ULL QuickPow(ULL x, ULL y) { ULL ans = 1; while (y) { if (y & 1) ans = (ans*x)%kMod; x = (x*x) % kMod; y >>= 1; } return ans; } int main() { int t, n, len; ULL ans; scanf("%d", &t); while (t–) { scanf("%d", &n); memset(visited, false, kMaxN); memset(prime_times, 0, kMaxN); for (int i = 1; i <= n; i++) scanf("%d", &permutation[i]); for (int i = 1; i <= n; i++) { if (!visited[i]) { visited[i] = true; int j = permutation[i]; len = 1; while (j != i) { visited[j] = true; j = permutation[j]; len++; } GetPrimeFactor(len); } } ans = 1; for (int i = 2; i < n; i++) if (prime_times[i] != 0) ans = (ans*QuickPow(i, prime_times[i])) % kMod; printf("%I64un", ans); } return 0; } [/cpp] 本代码提交AC,用时5101MS,内存27984K。]]>