分析
首先理解题意,目标求的式子为:[f(1)+f(2)+...+f(n)] mod f(m) mod p
,而由于n,m都为10^18^次方非常大我们只有对其式子进行化解取mod才能够取得最终结果,我们最终的方案为:矩阵快速幂+龟速乘法+分类讨论。
学习参考博客:AcWing 1213. 斐波那契
优化1:[f(1)+f(2)+...+f(n)]
=> f(n + 2) - 1
f(1) = f(3) - f(2)
f(2) = f(4) - f(3)
f(3) = f(5) - f(4)
...
f(n) = f(n + 2) - f(n + 1)
将f(1)+...+f(n) = f(n + 2) - f(2) = f(n + 2) - 1
此时目标式子为:[f(1)+f(2)+...+f(n)] mod f(m)
=> [f(n + 2) - 1] mod f(m)
。
我们现将[f(n + 2) - 1] mod f(m)
看作为整体f(n) mod f(m)
优化2:f(n) mod f(m)
=> f(n mod m) * f(m - 1)^n/m^
f(n) mod f(m)
n >= m
f(m + 1) = f(m) + f(m - 1) mod f(m) => f(m + 1) = f(m - 1)
f(m + 2) = f(m + 1) + f(m) mod f(m) => f(m + 2) = f(m + 1) = f(m - 1)
f(m + 3) = f(m + 2) + f(m + 1) mod f(m) => f(m + 3) = 2 * f(m - 1)
f(m + 4) = f(m + 3) + f(m + 2) mod f(m) => f(m + 4) = 3 * f(m - 1)
... 最终左边的系数即为f(k)
f(m + k) mod f(m) = f(k) * f(m - 1)
此时推出结论f(n) mod f(m) = f(m + k) = f(n - m) * f(m - 1)
又n可能>多个m乘积即:f(n - m) * f(m - 1)
f(n - 2m) * f(m - 1)^2
...
f(n mod m) * f(m - 1)^(n/m)
接着我们来针对于f(n mod m) * f(m - 1)^n/m^来继续进行化解,针对于 f(m - 1)^n/m^。
-
根据结论:f(n)^2^ = (-1)^(n+1)^ + f(n-1) * f(n+1)。
-
```java
//可以来尝试代入n=3计算
f(3)^2 = 4
(-1)^(3+1) + f(3-1) * f(3+1) = (-1)^4 + f(2) * f(4) = 1 + 3 = 4
//得证
//代入n=n-1,来尝试进行推导到f(n)^2
f(n - 1)^2 = (-1)^n + f(n - 2) * f(n)
= (-1)^n + [f(n) - f(n-1)] * f(n)
= (-1)^n + [f(n)]^2 - f(n - 1) * f(n)
//左右移项
[f(n)]^2 = (-1)^(n+1) + f(n-1)^2 + f(n) * f(n-1)
= (-1)^(n+1) + (f(n) + f(n - 1)) * f(n - 1)
= (-1)^(n+1) + f(n + 1) * f(n - 1) //推导成功
```
通过小结论f(n)^2^ = (-1)^(n+1)^ + f(n-1) * f(n+1),可以得到:f(m - 1)^2^ = (-1)^m^+ f(m - 2) * f(m)
f(m - 1)^2^是f(m - 1)^n/m^中的一部分,可以说是由若干个f(m - 1)^2^和f(m - 1)组成,这就需要进行额外讨论了,要看n/m为奇偶数情况。
此时我们要对f(n mod m) * f(m - 1)^n/m^进行分类讨论:
- 数/偶=奇、数/偶=偶。
情况1:当m为偶数时
①$n \over m$为偶数 【f(n mod m)】
此时就有偶数个f(m-1),[f(m-1)] ^n/m^ mod f(m),结果就为1。
f(n mod m) * f(m - 1)^n/m^ = f(n mod m)
②$n \over m$为奇数 【f(n mod m) * f(m-1)】
此时有奇数个f(m-1),此时[f(m-1)] ^n/m^同余为f(m-1)
f(n mod m) * f(m - 1)^n/m^ = f(n mod m) * f(m-1)
情况2:当m为奇数
①$n \over m$为偶数,$n \over 2m$为偶数 【 f(n mod m)】
此时有偶数个f(m-1),并且内部为偶数个–1乘
f(n mod m) * f(m - 1)^n/m^ = f(n mod m)
②$n \over m$为偶数,$n \over 2m$为奇数【f(m) - f(n mod m)】
偶数个f(m-1),有奇数个-1相乘
f(n mod m) * f(m - 1)^n/m^ = f(n mod m)*-1,又该数不能为负,最终要加上f(m),此时变为:
f(n mod m) * f(m - 1)^n/m^ = f(m) - f(n mod m)
③$n \over m$为奇数,$n \over 2m$为偶数【f(m - 1) * f(n mod m)】
此时由奇数个f(m - 1),偶数个-1相乘
f(n mod m) * f(m - 1)^n/m^ = f(m - 1) * f(n mod m)
④$n \over m$为奇数,$n \over 2m$为奇数 【f(m) - f(m - 1) * f(n mod m)】
此时由奇数个f(m - 1),奇数个-1相乘
f(n mod m) * f(m - 1)^n/m^ = -f(m - 1) * f(n mod m),有可能为负数,最终要加上f(m),此时变为:
f(n mod m) * f(m - 1)^n/m^ = f(m) - f(m - 1) * f(n mod m)
在上面分类讨论中你可以看到有类似于f(n) * f(m)的情况,由于题目给出的数据量十分大,可能就会造成溢出,所以我们这里需要将一个乘法转变为加法,在这个加法过程中来减少溢出的情况,即龟速乘法。
- a*b看做是b个a进行相加,即可对在过程中进行一个预处理a + 2a + 4a…+ 2^n-1^ * a
题解:矩阵快速幂+龟速乘法+分类讨论
复杂度分析:时间复杂度O(logn);空间复杂度O(1)
import java.util.*;
import java.io.*;
class Main {
static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
static long n, m, p;
//龟速乘法
//a*b => 例如5a a + 2a + 2a
static long qmul(long a, long b) {
long res = 0;
while (b != 0) {
if ((b & 1) == 1) res = (res + a) % p;
a = (a + a) % p;
b >>= 1;
}
return res;
}
//矩阵乘法
static void mul(long[][] a, long [][] b) {
//临时矩阵
long[][] temp = new long[2][2];
for (int i = 0; i < 2; i ++)
for (int j = 0; j < 2; j ++)
for (int k = 0; k < 2; k ++)
temp[i][j] = (temp[i][j] + qmul(a[i][k], b[k][j])) % p;
//拷贝
for (int i = 0; i < 2; i ++)
for (int j = 0; j < 2; j ++)
a[i][j] = temp[i][j];
}
//计算f(n)
static long F(long n) {
//极端情况
if (n == 0) return 0;
//根据fn来进行构造矩阵
//fn,分别为f(1) f(2)
long[][] f = {
{1, 1},
{0, 0}
};
//累乘矩阵
long[][] a = {
{0, 1},
{1, 1}
};
//快速幂
for (long k = n - 1; k != 0; k >>= 1){
if ((k & 1) == 1) mul(f, a);
mul(a, a);
}
return f[0][0];
}
//(F(m - 1) * F(n % m) - 1) mod F(m)
//(F(m - 1) * F(k) - 1) mod F(m)
public static long H(long m, long k) {
//若是n mod m为奇数
if (k % 2 == 1) return F(m - k) - 1;
else
{ // n mod m为偶数
//结论:f(m - 1)* f(k) = f(m) - f(m - k)
//判断f(m) - f(m - k)是否相等
//情况1:k == 0,f(m - k) = f(m)
//情况2:f(2) - f(1) = 0
if (k == 0 || m == 2 && m - k == 1) return F(m) - 1;
else return F(m) - F(m - k) - 1;
}
}
//F(n) - 1 % F(m)
static long G(long n, long m) {
//情况1:m为偶数
if (m % 2 == 0) {
//n/m是偶数 f(n mod m)
if (n / m % 2 == 0)
{
//特判情况
if (n % m == 0) return F(m) - 1;
else return F(n % m) - 1;
}else
{
// n/m为奇数 f(n mod m) * f(m-1)
return H(m, n % m);
}
}else { //情况2:m为奇数
//n/m为偶数,n/2m为偶数 f(n mod m)
if (n / m % 2 == 0 && n / (2 * m) % 2 == 0)
{
//特判
if (n % m == 0) return F(m) - 1;
else return F(n % m) - 1;
}
else if (n / m % 2 == 0 && n / (2 * m) % 2 == 1) //n/m为偶数,n/2m为奇数 f(m) - f(n mod m)
{
//特判f(m) - f(n mod m)为0情况 当f(m) == f(n % m),即m=2,n%m=1时
//f(m) - f(n mod m) = 0时
if (m == 2 && n % m == 1) return F(m) - 1;
else return F(m) - F(n % m) - 1;
}
else if (n / m % 2 == 1 && n / (2 * m) % 2 == 0) //n/m为奇数,n/2m为偶数 f(m - 1) * f(n mod m)
{
return H(m, n % m);
}
else
{
//n/m为奇数,n/2m为奇数 f(m) - f(m - 1) * f(n mod m)
//n mod m为奇数
if (n % m % 2 == 1)
{
if (m == 2 && m - n % m == 1) return F(m) - 1;
else return F(m) - F(m - n % m) - 1;
}else
{
//n mod m为偶数
//判断f(m - n mod m)是否为0
return F(m - n % m) - 1;
}
}
}
}
//判断是否读到空行
static boolean canRead() throws Exception{
String line = cin.readLine();
if (line == null || line.length() == 0) return false;
String[] ss = line.split(" ");
n = Long.valueOf(ss[0]);
m = Long.valueOf(ss[1]);
p = Long.valueOf(ss[2]);
return true;
}
public static void main(String[] args) throws Exception {
while (canRead()) {
//[f(n + 2) - 1] mod f(m)
System.out.println((G(n + 2, m) % p + p) % p);
}
}
}
哎哟我天那
大佬牛逼