株洲市网站关键词优化公司,做网站用别人的源码可以吗,免费建论坛,网站聚合页面怎么做UVA_10518 这个题目想到f(n)f(n-1)f(n-2)1还是比较容易的#xff0c;但如果能想到是f(n)2*F(n)-1就不太容易了#xff0c;在看了UVA的论坛之后我才知道原来可以表示成这个样子#xff0c;其中F(n)为斐波那契数#xff0c;有了这个式子是第一步#xff0c;后面的计算过程倒…UVA_10518 这个题目想到f(n)f(n-1)f(n-2)1还是比较容易的但如果能想到是f(n)2*F(n)-1就不太容易了在看了UVA的论坛之后我才知道原来可以表示成这个样子其中F(n)为斐波那契数有了这个式子是第一步后面的计算过程倒还不算麻烦。 后来在群里讨论的时候突然发现S(n)F(n)F(n1)-1S(n)为斐波那契的前n项和这时又想到我之前推到的一个结论f(n)S(n)-F(n-1)发现这个和f(n)2*F(n)-1是可以转化的限于当时还不知道S(n)的表达式所以错过了推出结论的机会。 先说说我推出f(n)S(n)-F(n)的过程吧我们在递推计算递归次数的时候每次的1都另起一行来写这样我们会得到下面的这个表。 f(0) f(1) f(2) f(3) f(4) f(5) f(6) 1 1 1 1 1 2 1 1 2 3 1 1 2 3 5 1 1 2 3 5 8 13 没有数字的地方就可以看做是0f(i)下面对应的整数和就是f(i)的值相当于计算f(n)f(n-1)f(n-2)1的时候每行都进行f(n)f(n-1)f(n)的运算最后再把1另起一行写在上面。 这样我们就能很明显的看出来每行都是一个斐波那契数列不难得到f(n)S(n)-F(n-1)这样再把S(n) F(n)F(n1)-1代入就可以得到f(n)2*F(n)-1。 不管用什么办法反正我们现在是得到f(n)的表达式了。下面回到题目问题就转化成了f(n)%b的值是多少由于n很大所以我们在计算F(n)的时候不能直接递推计算于是可以把F(n)写成矩阵的形式然后用快速幂取模求得F(n)%b的值进而就会有f(n)%b的值。 #includestdio.h#includestring.h#includemath.hlong long int N, B;long long int a[100][5], b[5];void pow_mod(long long int n, int e){if(n 1) { a[e][0] a[e][1] a[e][2] 1; a[e][3] 0;return ; } pow_mod(n / 2, e 1); a[e][0] (a[e 1][0] * a[e 1][0] a[e 1][1] * a[e 1][2]) % B; a[e][1] (a[e 1][0] * a[e 1][1] a[e 1][1] * a[e 1][3]) % B; a[e][2] (a[e 1][2] * a[e 1][0] a[e 1][3] * a[e 1][2]) % B; a[e][3] (a[e 1][2] * a[e 1][1] a[e 1][3] * a[e 1][3]) % B;if(n % 2) { b[0] (a[e][0] * a[0][0] a[e][1] * a[0][2]) % B; b[1] (a[e][0] * a[0][1] a[e][1] * a[0][3]) % B; b[2] (a[e][2] * a[0][0] a[e][3] * a[0][2]) % B; b[3] (a[e][2] * a[0][1] a[e][3] * a[0][3]) % B; a[e][0] b[0], a[e][1] b[1], a[e][2] b[2], a[e][3] b[3]; }}void solve(){ a[0][0] a[0][1] a[0][2] 1; a[0][3] 0;if(N 0) { printf(1\n);return ; } pow_mod(N, 1); printf(%lld\n, (2 * a[1][0] B - 1) % B);}int main(){int t 0;for(;;) { scanf(%lld%lld, N, B);if(!N !B)break; printf(Case %d: %lld %lld , t, N, B); solve(); }return 0;} 转载于:https://www.cnblogs.com/staginner/archive/2011/12/14/2288187.html
