CC

自然万物都趋向从有序变得无序

0%

So Easy! HDU - 4565 矩阵快速幂

发表于 更新于 分类于 Valine：

题目链接:点我

题目

　A sequence S n 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 S n.
　　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 S n.

Sample Input

2 3 1 2013
2 3 2 2013
2 2 1 2013

Sample Output

4
14
4

题意:

如同题目公式描述的那样.

思路:

矩阵快速幂,
我们设 x, y为未知数,那么(a+b)n(a + \sqrt b) ^{n} = x + y * b\sqrt b 的形式,其他x, y为整数,又因为(a−1)2(a-1)^ 2< b <$ a^ 2$ ,那么a - 1 $\lt \sqrt b \lt $ a,于是ceil(b\sqrt b) = a; 于是 (a−b)n<(a - \sqrt b)^n \lt 1,而它与(a+b)n(a + \sqrt b) ^{n} 相加后展开式中会抵消掉待有根号的项, 而我们又知道 (a+b)n+1(a + \sqrt b) ^{n + 1} =$x_{n+1} + y_{n+1} * \sqrt b $ = ( xn+yn∗bx_n + y_n* \sqrt b ) *($ a + \sqrt b$) = (xn∗a+ynb)+(a∗yn+xn)∗b(x_n * a + y_n b) + (a * y_n + x_n) * \sqrt b由此我们可以构造出递推式, xn+1=xn∗a+yn∗bx_{n+1} = x_n * a + y_n * b, yn+1=xn+yn∗ay_{n+1} = x_n + y_n * a;
又因为我们知道(a+b)n+(a−b)n=2∗xn(a + \sqrt b) ^{n} + (a - \sqrt b) ^{n} = 2 * x_n, 而且(a−b)n<(a - \sqrt b)^n \lt 1,所以ceil((a+b)n(a + \sqrt b) ^{n}) = 2∗xn2 * x_n,

代码:

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
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;

typedef long long LL;
LL a, b,n, m;
struct mat{
    LL a[3][3];
    mat(){memset(a, 0, sizeof(a)); }
    mat operator *(const mat q){
        mat c;
        for(int i = 1; i <= 2; ++i)
            for(int j = 1; j <= 2; ++j)
            if(a[i][j])
        for(int k = 1; k <= 2; ++k){
            c.a[i][k] += a[i][j] * q.a[j][k];
            if (c.a[i][k] >= m) c.a[i][k] %= m;
        }return c;
    }
};

mat qpow(mat x, LL n){
    mat ans;
    ans.a[1][1] = ans.a[2][2] = 1;
    while(n){
        if (n&1) ans = ans * x;
        x = x * x;
        n >>= 1;
    }return ans;
}


int main(){
    while(scanf("%lld %lld %lld %lld", &a, &b, &n, &m) != EOF){
        mat ans;
        a = a % m;
        b = b %m;
        ans.a[1][1] = ans.a[2][2] =a;
        ans.a[1][2] =  b;
        ans.a[2][1] = 1;
        ans = qpow(ans, n);
        LL sum = ans.a[1][1];
        sum = (sum * 2) % m;
        printf("%lld\n",sum);
    }return 0;
}