目录

〇，模板

一，快速乘法

CSU 1162 Balls in the Boxes

HDU 5187 zhx's contest 

二，快速幂

POJ 1995 Raising Modulo Numbers

力扣 50. Pow(x, n) 

力扣 剑指 Offer 14- I/14- II. 剪绳子 343. 整数拆分

力扣 372. 超级次方

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

力扣 1922. 统计好数字的数目

力扣 1969. 数组元素的最小非零乘积

力扣 2580. 统计将重叠区间合并成组的方案数

CSU 1198 Staginner the Caster

CSU 1413 Area of a Fractal（分形图形面积）

三，矩阵快速幂

CSU 1752 童话故事生成器

CSU 1769 想打架吗？算我一个！所有人，都过来！(3) 

CSU 1313 ZZY的宠物

CSU 1895 Apache is late again(根号2加1的n次方) 

CSU 2138 Rikka's Set 

POJ 3233 Matrix Power Series

UESTC 278 Fibonacci

HDU 1575 Tr A

UVA 12470 Tribonacci

力扣 552. 学生出勤记录 II

四，矩阵快速幂总结

讯享网

〇，模板

参考 快速幂

一，快速乘法

CSU 1162 Balls in the Boxes

Description

Mr. Mindless has many balls and many boxes,he wants to put all the balls into some of the boxes.Now, he wants to know how many different solutions he can have.

you know,he could put all the balls in one box,and there could be no balls in some of the boxes.Now,he tells you the number of balls and the numbers of boxes, can you to tell him the number of different solutions? Because the number is so large, you can just tell him the solutions mod by a given number C.

Both of boxes and balls are all different.

Input

There are multiple testcases. In each test case, there is one line cantains three integers:the number of boxes ,the number of balls,and the given number C separated by a single space.All the numbers in the input are bigger than 0 and less than 2^63.

Output

 For each testcase,output an integer,denotes the number you will tell Mr. Mindless

Sample Input

3 2 4 4 3 5

Sample Output

讯享网1 4

代码：

#include<iostream> using namespace std; #define ll long long ll g(ll a, ll b, ll p)//a*b { if (b == 0)return 0; ll r = g(a, b / 2, p); r = (r + r) % p; if (b % 2)r = (r + a) % p; return r; } ll f(ll a, ll b, ll p)//a^b { if (b == 0)return 1; ll r = f(a, b / 2, p); r = g(r, r, p); if (b % 2)r = g(r, a, p); return r; } int main() { ll a, b, p; while (cin >> a >> b >> p)cout << f(a, b, p) << endl; return 0; }

​

HDU 5187 zhx's contest 

As one of the most powerful brushes, zhx is required to give his juniors nn problems.
zhx thinks the ithith problem's difficulty is ii. He wants to arrange these problems in a beautiful way.
zhx defines a sequence {ai}{ai} beautiful if there is an ii that matches two rules below:
1: a1..aia1..ai are monotone decreasing or monotone increasing.
2: ai..anai..an are monotone decreasing or monotone increasing.
He wants you to tell him that how many permutations of problems are there if the sequence of the problems' difficulty is beautiful.
zhx knows that the answer may be very huge, and you only need to tell him the answer module pp.

Input

Output

For each test case, output a single line indicating the answer.

Sample Input

讯享网2 233 3 5

Sample Output

2 1 

Hint

讯享网In the first case, both sequence {1, 2} and {2, 1} are legal. In the second case, sequence {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1} are legal, so the answer is 6 mod 5 = 1

经过数学求解之后，这题其实就是：

输入n,p，输出(2^n-2)%p

这就需要快速乘法和快速幂了。

代码：

#include <iostream> using namespace std; long long n, p; template<typename A,typename N> A aijiMulti(A a, N n, A(*pfunc)(A,A)); template<typename A> A opAdd(A x, A y) { return (x+y)%p; } template<typename A> A opMulti(A x, A y) { return aijiMulti(x,y,opAdd); } template<typename A,typename N> A aijiMulti(A a, N n, A(*pfunc)(A,A)) { if(n<=1)return a; A ans = aijiMulti(a, n/2, pfunc); ans = pfunc(ans,ans); if(n%2)ans = pfunc(ans,a); return ans; } int main() { while(cin>>n>>p){ long long ans = aijiMulti((long long)2,n,opMulti<long long>); cout<<((ans-2)%p+p)%p<<endl; } return 0; }