uva 10518 - How Many Calls?（矩阵快速幂）

╰半夏微凉° 2022-05-12 23:16 143阅读 0赞

[题目链接：uva 10518 - How Many Calls?][uva 10518 - How Many Calls]

公式f(n) = 2 \* F(n) - 1, F(n)用矩阵快速幂求。

#include <stdio.h>
    #include <string.h>
    long long n;
    int b;
    
    struct state {
    	int s[2][2];
    	state(int a = 0, int b = 0, int c = 0, int 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 cas = 1;
    	while (scanf("%lld%d", &n, &b), n || b) {
    		state ans = solve(n);
    		printf("Case %d: %lld %d %d\n", cas++, n, b,(2 * ans.s[0][0] - 1 + b) % b);
    	}
    	return 0;
    }

[uva 10518 - How Many Calls]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=115&page=show_problem&problem=1459

发表评论取消回复

表情：

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

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

相关阅读

相关 uva 10061——How many zero\'s and how many digits ?

题意：这道题开始是卡了很久的，题意是给定一个数n然后让你求B进制下n！有多少个零，和有多少位数，咋一看，是高精度，如果数论不是很熟系。思路：开始是直接抛弃高精度的一

傷城~/ 2022年08月09日 13:49/ 0 赞/ 19 阅读

相关 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 赞/ 153 阅读

相关快速幂，矩阵快速幂（模板）

1，整数快速幂： C++ Code <table style="width:100%;font-family:Consolas, 'Courier New';font-

左手的ㄟ右手/ 2022年06月11日 03:57/ 0 赞/ 312 阅读

相关【矩阵快速幂】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 赞/ 158 阅读

相关【矩阵幂的和+矩阵快速幂】Power of Matrix UVA - 11149

Think: 1知识点：矩阵幂的和+矩阵快速幂 2题意：输入矩阵A，求A^1 + A^2 + … + A^(n) 3题意分析：（1）：倍增法求矩阵幂的和，eg

本是古典何须时尚/ 2022年06月07日 06:09/ 0 赞/ 200 阅读

相关【循环矩阵+矩阵快速幂】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 赞/ 146 阅读

相关 UVA 11551(矩阵快速幂)

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

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

相关 uva 696 - How Many Knights

[题目链接：uva 696 - How Many Knights][uva 696 - How Many Knights] 题目大意：给出一个n \ m的网格，计算

刺骨的言语ヽ痛彻心扉/ 2022年05月12日 23:26/ 0 赞/ 106 阅读

相关 uva 10518 - How Many Calls?（矩阵快速幂）

[题目链接：uva 10518 - How Many Calls?][uva 10518 - How Many Calls] 公式f(n) = 2 \ F(n) -

╰半夏微凉°/ 2022年05月12日 23:16/ 0 赞/ 144 阅读

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

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

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