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+yn∗6
(
5
−
2
6
)
n
=
x
n
−
y
n
∗
6
(5 - 2sqrt 6)^n = x_n - y_n * sqrt 6
(5−26)n=xn−yn∗6
因为
(
5
−
2
6
)
<
1
(5 - 2sqrt 6) <1
(5−26)<1 ,所以
(
5
−
2
6
)
n
<
1
(5 - 2sqrt 6)^n < 1
(5−26)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+(5−6)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)=2∗xnn
所以
f
l
o
o
r
(
s
n
)
=
2
∗
x
n
−
1
floor(s_n) = 2*x_n - 1
floor(sn)=2∗xn−1
这样我们只需构造出矩阵求出 x n x_n xn 就行了
s
n
=
s
n
−
1
∗
(
5
+
2
6
)
s_n = s_{n-1} * (5+ 2sqrt 6)
sn=sn−1∗(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+yn∗6=(5xn−1+12yn−1)+(2xn−1+5yn−1)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内容请搜索靠谱客的其他文章。
发表评论 取消回复