本文是2017年北京邮电大学第十一届程序设计竞赛网络热身赛的F. Simple recursion题解。
题目
题目描述 r_clover shows you a BIIIIIIIIIIG water problem: if \(f(0)=1,f(1)=1\),\(f(n)=2f(n-1)+3f(n-2)\), what is \(f(n)mod1000000007\)?
输入格式 A single integer n(0≤n≤10000000000).
输出格式 A single integer, which is the answer for f(n)mod1000000007.
输入样例 10 输出样例 29525
思路
一开始想的是用递归。但经测试发现递归的时间、空间复杂度都太高，导致超时。
正确打开方式：求出递推关系，并用快速幂取模方法计算结果。
递推关系求解
《组合数学》内容————常系数线性齐次递推关系的求解。公式见后面的附1。 求解题目中所给的递推关系： \[f(n)=2f(n-1)+3f(n-2)\] \[f(0)=1,f(1)=1\] 它的特征方程为： \[x^2-2x-3=0\] 解方程得： \[x_1=3,x_2=-1\] 所以递推关系的通解为： \[f(n)=c_13^n+c_2(-1)^n\] 代入初值\(f(0)=1,f(1)=1\)，得到： \[f(0)=c_1+c_2=1\] \[f(1)=3c_1-c_2=1\] 解得:\(c_1=c_2=0.5\) 因此该递推关系的解为\[f(n)=0.5(3)^n+0.5(-1)^n\]
代码实现：
1
2
3
4
5
6
7
8
9
10
long f(long long n,int modNum){
long long a=3;
long long b=1;
a= quick_algorithm(a,n,modNum);//(a的n次方)mod(modNum),是快速求幂取模的方法，详细见后面的推导
if(n%2==1){
b=-1;
}
a=0.5*a+0.5*b;
return a;
}
常系数线性齐次递归关系的求解
递推关系：
\[f(n)=c_1f(n-1)+c_2f(n-2)+...+c_kf(n-k)\]
递推关系的特征方程：
\[x^k-c_1x^{k-1}-c_2x^{k-2}-...-c_k=0\]
递归关系的特征根：
特征方程的k个根（可能重根）：\[q_1,q_2,...,q_k\]
递归关系的特解：
设q是非零复数，则\(f(n)=q^n\)是递推关系的解，当且仅当q是它的特征根。
递归关系的通解：
设\(q_1,q_2,...,q_k\)是递推关系的k个互不相等的特征根，则 \[f(n)=b_1q_1^n+b_2q_2^n+b_3q_3^n+...+b_kq_k^n\]是递推关系的通解。
快速大数幂运算
这是一种很神奇的方法。
首先引入一些基础知识。
幂取模运算的一个性质
\[(a\times b)mod(c)=(((a)mod(c))\times ((b) mod(c)))mod(c)\]
大数幂运算 核心思想：将大数的幂运算拆解成了相对应的乘法运算，利用上面的式子，始终将我们的运算的数据量控制在c的范围以下。
对于目标： \[a^bmodc\] 我们将b表示为二进制： \[b=b_0+b_12+b_22^2+...+b_n2^n\] 那么， \[a^b=a^b_1\times a^{b_22^2} \times a^{b_32^3} \times ... \times a^{b_n2^n}\] 其中\(b_k\)要么为0，要么为1 去掉所有的0后，我们得到 \[a^b=a^{b_k2^k} \times ... \times a^{b_n2^n}\] 上式的模可以表示为： \[a^b mod c =a^{b_k2^k} mod c\times ... \times a^{b_n2^n}mod c\] 易发现： \[A_k=a^{b_k2^k} mod c\] \[...\] \[A_n=a^{b_n2^n} mod c\]
即：\(A(n)\)是\(A(n-1)\)的平方倍！
实现：
1
2
3
4
5
6
7
8
9
10
11
12
int quick(int a,int b,int c)
{
int ans=1; //记录结果
a=a%c; //预处理，使得a处于c的数据范围之下
while(b!=0)
{
if(b&1) ans=(ans*a)%c; //如果b的二进制位不是0，那么我们的结果是要参与运算的
b>>=1; //二进制的移位操作，相当于每次除以2，用二进制看，就是我们不断的遍历b的二进制位
a=(a*a)%c; //不断的加倍
}
return ans;
}
代码
#include <iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include <math.h>
using namespace std;
long quick_algorithm(long long a,long long n,int modNum){
a=a%modNum ;
long long ans=1 ;
//这里我们不需要考虑b<0，因为分数没有取模运算
while(n!=0){
if(n&1)
ans=(ans*a)%modNum ;
n>>=1 ;
a=(a*a)%modNum;
}
return ans;
}
long set2(long long n,int modNum){
long long a=3;
long long b=1;
/*for(long long i=0;i<n;i++){
a=a*3;
a=a%modNum;
}*/
a= quick_algorithm(a,n,modNum);
if(n%2==1){
b=-1;
}
//a=a;
a=0.5*a+0.5*b;
return a;
}
int main()
{
int modNum=1000000007;
long long input=999999999;
scanf("%lld",&input);
if(input==0||input==1){
printf("%lld\n",1);
}else{
long long out=set2(input,modNum);
printf("%lld\n",out);
}
return 0;
}参考文献
- 《组合数学引论》
附上本题的艰辛史。 