uva 10229 - Modular Fibonacci(矩阵快速幂）

梦里梦外; 2022-05-12 23:16 131阅读 0赞

[题目链接：uva 10229 - Modular Fibonacci][uva 10229 - Modular Fibonacci]

题目大意：给出n和m，求出f(n) %m, f(x)为斐波那契数列。

解题思路：因为n的范围在0~214783647，所以计算量比较大，所以用矩阵快速幂。

\{(1, 1), (1, 0)\} ^ n \*（f\[1\], f\[0\]) = (f\[n\], f\[n - 1\]).

#include <stdio.h>
    #include <math.h>
    long long n, b, k;
    
    struct state {
    	long long s[2][2];
    	state(long long a = 0, long long b = 0, long long  c = 0, long long d = 0) {
    		s[0][0] = a, s[0][1] = b, s[1][0] = c, s[1][1] = d;
    	}
    }tmp(1, 0, 0, 1), c(1, 1, 1, 0);
    
    state count(const state& p, const state& q) {
    	state f;
    	for (int i = 0; i < 2; i++)
    		for (int j = 0; j < 2; j++)
    			f.s[i][j] = (p.s[i][0] * q.s[0][j] + p.s[i][1] * q.s[1][j]) % b;
    	return f;
    }
    
    state solve(long long k) {
    	if (k == 0) return tmp;
    	else if (k == 1) return c;
    
    	state a = solve(k / 2);
    
    	a = count(a, a);
    	if (k % 2) a = count(a, c);
    	return a;
    }
    
    int main () {
    	int m;
    	while (scanf("%lld%d", &n, &m) == 2) {
    		b = pow(2, m);
    		if (n) {
    			state ans = solve(n - 1);
    			k = ans.s[0][0];
    		} else
    			k = 0;
    		printf("%lld\n", k);
    	}
    	return 0;
    }

[uva 10229 - Modular Fibonacci]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=115&page=show_problem&problem=1170

发表评论取消回复

表情：

评论列表（有 0 条评论，131人围观）

还没有评论，来说两句吧...

相关阅读

相关 poj 3070 Fibonacci 矩阵快速幂

include <cstdio> include <cstring> using namespace std; define M_H

谁借莪１个温暖的怀抱￠/ 2022年08月08日 05:21/ 0 赞/ 148 阅读

相关 UVA 12297 Super Poker（矩阵快速幂）

想到了一个递推式 f(n,k)=f(n−k,k)\+f(n−k,k−1)∗4\+f(n−k,k−2)∗6\+f(n−k,k−3)∗4\+f(n−k,k−4) 这

向右看齐/ 2022年08月05日 05:10/ 0 赞/ 112 阅读

相关 UVa11582 - Colossal Fibonacci Numbers! （快速幂取模）

输入两个非负数 a，b，和正整数n，计算f（a^b）除以n的余数； f（i+2） = f（i+1） + f（i）; 函数f里是一个斐波那契数，所以需要打表，但是由于数

阳光穿透心脏的1/2处/ 2022年06月08日 09:28/ 0 赞/ 140 阅读

相关【矩阵快速幂】Recurrences UVA - 10870

Think: 1知识点：矩阵快速幂 2题意：![这里写图片描述][SouthEast] 现输入d, n, m求解f(n) 注：f(i) = f(i) mod m

Love The Way You Lie/ 2022年06月07日 08:35/ 0 赞/ 124 阅读

相关【循环矩阵+矩阵快速幂】Cellular Automaton UVA - 1386

Think: 1知识点：循环矩阵+矩阵快速幂 2题意：输入n(1<=n<=500), m(1<=n<=1000000), d(0<=d<(n/2)), k(1<=k<=

╰+哭是因爲堅強的太久メ/ 2022年06月06日 20:45/ 0 赞/ 114 阅读

相关 UVA 11551(矩阵快速幂)

题目来源:[点击打开链接][Link 1] 题目题意:题目给我们n个数和r次操作。接在输入n行，表示每次将第i个数变成它后面几个位置的和。重复r次。题目分析:我们按照题目

缺乏、安全感/ 2022年06月04日 05:16/ 0 赞/ 160 阅读

相关 poj Fibonacci 矩阵快速幂

题目链接：[点我][Link 1] Description In the Fibonacci integer sequence, F0 = 0, F1 = 1, and

向右看齐/ 2022年05月16日 11:22/ 0 赞/ 163 阅读

相关 uva 10229 - Modular Fibonacci(矩阵快速幂）

[题目链接：uva 10229 - Modular Fibonacci][uva 10229 - Modular Fibonacci] 题目大意：给出n和m，求出f

梦里梦外;/ 2022年05月12日 23:16/ 0 赞/ 132 阅读

相关 POJ 3070 Fibonacci——————矩阵快速幂解法

\\Fibonacci \\ Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 19481 Acce

浅浅的花香味﹌/ 2022年05月10日 11:34/ 0 赞/ 147 阅读

相关 POJ3070Fibonacci（矩阵快速幂）

在斐波那契数列中，Fib0=0,Fib1=1,Fibn=Fibn−1+Fibn−2(n>1) 。给定整数n，求Fibnmod10000 。输入格式输入包含多组

小咪咪/ 2021年10月25日 12:22/ 0 赞/ 297 阅读