hdu 4565 So Easy!（矩阵乘法+共轭公式）

本文主要是介绍hdu 4565 So Easy!（矩阵乘法+共轭公式），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem Description
　　A sequence Sn is defined as:

Where a, b, n, m are positive integers.┌x┐is the ceil of x. For example, ┌3.14┐=4. You are to calculate Sn.
　　You, a top coder, say: So easy!

Input
　　There are several test cases, each test case in one line contains four positive integers: a, b, n, m. Where$0< a, m < 2^{15} , (a-1)^2< b < a^2, 0 < b, n < 2^{31}$.The input will finish with the end of file.

Output
　　For each the case, output an integer Sn.

Sample Input
2 3 1 2013
2 3 2 2013
2 2 1 2013

Sample Output
4
14
4

Source
2013 ACM-ICPC长沙赛区全国邀请赛——题目重现

题目让求 $(a+\sqrt b)^n$ 向上取整
因为出现了根号和向上取整，所以我们可以往凑整数方面想。
$(a+ \sqrt b)^n = x_n + y_n * \sqrt b$
$(a- \sqrt b)^n = x_n - y_n * \sqrt b$
$(a-1)^2 < b < a^2 ,且 n > 1$，所以$(a-\sqrt b)^n< 1$
所以$ceil(s_n) = (a+\sqrt b)^n + (a-\sqrt b)^n$
所以 $ceil(s_n) = 2*x_n$

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

$s_n = s_{n-1} * (a+ \sqrt b)$
$x_n + y_n * \sqrt b = (ax_{n-1}+by_{n-1})+(x_{n-1}+ay_{n-1})\sqrt b$

所以矩阵为：
$\bigl( \begin{smallmatrix} x_1 & y_1 \\ 0 & 0 \end{smallmatrix} \bigr) \bigl( \begin{smallmatrix} a & 1 \\ b & a \end{smallmatrix} \bigr)$

$x_1 = a, y_1 = 1$

另一篇是hdu2256，是向下取整，可以一起看看。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;LL mod;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,LL 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)
{LL a,b,n,m;while(scanf("%lld%lld%lld%lld",&a,&b,&n,&m)==4){mod = m;LL aa[2][2] = { a,1LL,0LL,0LL};Matrix A(2,aa);LL bb[2][2] = { a%mod,1LL,b%mod,a%mod};Matrix B(2,bb);Matrix ans = A*(B^(n-1));printf("%d\n",ans.m[0][0]*2%mod);}return 0;
}

这篇关于hdu 4565 So Easy!（矩阵乘法+共轭公式）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---