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

150 阅读 0 评论 99 点赞

我是靠谱客的博主儒雅小笼包，这篇文章主要介绍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("%dn",ans.m[0][0]*2%mod);
    }

return 0;
}

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
#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("%dn",ans.m[0][0]*2%mod);
    }

    return 0;
}