HDU （2855 Fibonacci Check-up）

spoiler posted @ 2011年4月26日 20:57 in 十个利用矩阵乘法解决的经典题目 , 1925 阅读

题目大意：

这个是组合数，然后求给定N,P让你求 $\sum_{k=0}^{n}{C_n^k}{f[k]}$ mod p的值是多少

题目分析：

第一种方法：这里我引用一种常见的母函数：

（a+1）^n= ${C_n^0}$ + ${C_n^1}$ *a^1+ ${C_n^2}$ *a^2+....+ ${C_n^n}$ *a^n;

这里我可以知道fibonacci数可以用mitrax= $\begin{bmatrix}1 & 1\\1 & 0\end{bmatrix}$ 的乘积表示，f[i]=mitrax^i;

这里我们的“1”可以用 $\begin{bmatrix}1 & 0\\0 & 1\end{bmatrix}$ 表示即单位矩阵，这样我们只要求两个矩阵的的 i 次幂就可以了，这就直接转换到矩阵的二分法求快速幂上来了！注意一点，最后输出的[1][2]这个位置的数，别输出错了！

第二种方法：

$\sum_{k=0}^{n}{C_n^k}{f[k]}$ 最后证明结论等于： $\sum_{k=0}^{n}{C_n^k}{f[k]}$ = F[ 2* N ]

引进fibonacci数的计算方程：

$\sum_{k=0}^{n}{C_n^k}{f[k]}$ ={ $\sum_{k=0}^{n}{C_n^k}$ *( $\frac{1+\sqrt{5}}{2}$ )^k -( $\frac{1-\sqrt{5}}{2}$ )^k}

因为：

（a+1）^n= $\sum_{k=0}^{n}{C_n^k}$ *a^k;

所以将上式化简成：

$\sum_{k=0}^{n}{C_n^k}{f[k]}$ =（ $\frac{3+\sqrt{5}}{2}$ ）^n+( $\frac{3-\sqrt{5}}{2}$ )^n

分子分母都乘*2 =( $\frac{6+2*\sqrt{5}}{4}$ )^n+( $\frac{6-2*\sqrt{5}}{4}$ )^n

=( $\frac{1+\sqrt{5}}{2}$ )^2n+( $\frac{1-\sqrt{5}}{2}$ )^2n

=F[ 2*N ]

我的代码是第一种的：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct M {
	int s[3][3];
};
int p;
struct M multiply(struct M a,struct M b){
	struct M c;
	memset(c.s,0,sizeof(c.s));
	for(int i=1;i<=2;i++)
		for(int j=1;j<=2;j++)
			for(int k=1;k<=2;k++)
				c.s[i][j]=(c.s[i][j]+(a.s[i][k]*b.s[k][j])%p)%p;
	return c;
}
struct M paw(struct M a,int t){
	if(t==1)
		return a;
	else{
		struct M b=paw(a,t/2);
		if(t&1){
			return multiply(multiply(b,b),a);
		}
		else
			return multiply(b,b);
	}
}
int main(){
	struct M a,b;
	int n,cas;
	a.s[1][1]=2;	a.s[1][2]=1;
	a.s[2][1]=1;	a.s[2][2]=1;
	/*b.s[1][1]=1;	b.s[1][2]=0;
	b.s[2][1]=0;	b.s[2][2]=1;*/
	scanf("%d",&cas);
	while(cas--){
		scanf("%d %d",&n,&p);
		if(n==0)
		{	printf("0\n");	continue;	}
		b=paw(a,n);
		printf("%d\n",b.s[1][2]);
	}
	return 0;

}

文章总结：（a+1）^n= $\sum_{k=0}^{n}{C_n^k}$ *a^k;这个母函数很好用下次记得灵活运用！