Tag Archives: 快速幂

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}
完整代码如下:

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

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

hihoCoder 1504-骑士游历

hihoCoder 1504-骑士游历

#1504 : 骑士游历

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

描述

在8x8的国际象棋棋盘上给定一只骑士(俗称“马”)棋子的位置(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行即可,没必要再构造一个只含一个元素的矩阵,再左乘了。

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

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

LeetCode Pow(x, n)

LeetCode Pow(x, n)
Implement pow(x, n).


实现幂指数运算。
如果对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。

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就是快速幂取模了。
完整代码如下:

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

本代码提交AC,用时5101MS,内存27984K。