HDU (2855 Fibonacci Check-up)

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

题目大意:

这个是组合数,然后求给定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;这个母函数很好用 下次记得灵活运用!


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter