我是靠谱客的博主 默默老鼠,这篇文章主要介绍hdu 2256 Problem of Precision(矩阵乘法+共轭公式),现在分享给大家,希望可以做个参考。

Problem Description

这里写图片描述

Input
The first line of input gives the number of cases, T. T test cases follow, each on a separate line. Each test case contains one positive integer n. (1 <= n <= 10^9)

Output
For each input case, you should output the answer in one line.

Sample Input
3
1
2
5

Sample Output
9
97
841

Source
HDOJ 2008 Summer Exercise(4)- Buffet Dinner

题目让求 ( 2 + 3 ) 2 n (sqrt 2 + sqrt 3)^{2n} (2 +3 )2n
就是求 ( 5 + 2 6 ) n (5 +2 sqrt 6)^n (5+26 )n

因为出现了根号和向上取整,所以我们可以往凑整数方面想。
( 5 + 2 6 ) n = x n + y n ∗ 6 (5+ 2sqrt 6)^n = x_n + y_n * sqrt 6 (5+26 )n=xn+yn6
( 5 − 2 6 ) n = x n − y n ∗ 6 (5 - 2sqrt 6)^n = x_n - y_n * sqrt 6 (526 )n=xnyn6
因为 ( 5 − 2 6 ) &lt; 1 (5 - 2sqrt 6) &lt;1 (526 )<1 ,所以 ( 5 − 2 6 ) n &lt; 1 (5 - 2sqrt 6)^n &lt; 1 (526 )n<1
所以 c e i l ( s n ) = ( 5 + 6 ) n + ( 5 − 6 ) n ceil(s_n) = (5+sqrt 6)^n + (5-sqrt 6)^n ceil(sn)=(5+6 )n+(56 )n
又因为 s n s_n sn 不为整数,所以
所以 f l o o r ( s n ) = c e i l ( s n ) − 1 floor(s_n) = ceil(s_n) - 1 floor(sn)=ceil(sn)1
因为 c e i l ( s n ) = 2 ∗ x n n ceil(s_n) = 2*x_nn ceil(sn)=2xnn
所以 f l o o r ( s n ) = 2 ∗ x n − 1 floor(s_n) = 2*x_n - 1 floor(sn)=2xn1

这样我们只需构造出矩阵求出 x n x_n xn 就行了

s n = s n − 1 ∗ ( 5 + 2 6 ) s_n = s_{n-1} * (5+ 2sqrt 6) sn=sn1(5+26 )
x n + y n ∗ 6 = ( 5 x n − 1 + 12 y n − 1 ) + ( 2 x n − 1 + 5 y n − 1 ) 6 x_n + y_n * sqrt 6 = (5x_{n-1}+12y_{n-1})+(2x_{n-1}+5y_{n-1})sqrt 6 xn+yn6 =(5xn1+12yn1)+(2xn1+5yn1)6

所以矩阵为:
KaTeX parse error: No such environment: smallmatrix at position 14: bigl( begin{̲s̲m̲a̲l̲l̲m̲a̲t̲r̲i̲x̲}̲ x_1 & y_1 \ 0…

$x_1 = 5, y_1 = 2 $

另一篇是 hdu 4565,是向上取整,可以一起看一下。
(http://blog.csdn.net/ssimple_y/article/details/76614336)

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define LL long long using namespace std; int mod = 1024; struct Matrix { long long m[2][2]; int n; Matrix(int x) { n = x; for(int i=0;i<n;i++) for(int j=0;j<n;j++) m[i][j] = 0; } Matrix(int _n,int a[2][2]) { n = _n; for(int i=0;i<n;i++) for(int j=0;j<n;j++) { m[i][j] = a[i][j]; } } }; Matrix operator *(Matrix a,Matrix b) { int n = a.n; Matrix ans = Matrix(n); for(int i=0;i<n;i++) for(int j=0;j<n;j++) for(int k=0;k<n;k++) { ans.m[i][j] += (a.m[i][k]%mod)*(b.m[k][j]%mod)%mod; ans.m[i][j] %= mod; } return ans; } Matrix operator ^(Matrix a,int k) { int n = a.n; Matrix c(n); int i,j; for(i=0;i<n;i++) for(j=0;j<n;j++) c.m[i][j] = (i==j); for(;k;k>>=1) { if(k&1) c=c*a; a = a*a; } return c; } int main(void) { int T,n; scanf("%d",&T); int a[2][2] = { 5,2, 0,0}; Matrix A(2,a); int b[2][2] = { 5,2, 12,5}; Matrix B(2,b); while(T--) { scanf("%d",&n); Matrix ans = A*(B^(n-1)); printf("%dn",(ans.m[0][0]*2-1)%mod); } return 0; }

最后

以上就是默默老鼠最近收集整理的关于hdu 2256 Problem of Precision(矩阵乘法+共轭公式)的全部内容,更多相关hdu内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(89)

评论列表共有 0 条评论

立即
投稿
返回
顶部