首页 > ACM题库 > HDU-杭电 > HDU 4656-Evaluation-递推-[解题报告]HOJ
2015
09-17

HDU 4656-Evaluation-递推-[解题报告]HOJ

Evaluation

问题描述 :

xk=b*c(2k)+d
F(x)=a0 x0+a1 x1+a2 x2+…+an-1 xn-1
Given n, b, c, d, a0, …, an-1, calculate F(x0), …, F(xn-1).

输入:

There is only one test case.
First line, four integers, n, b, c, d.
Second line, n integers, a0, …, an-1.

1<=n<=105
1<= b, c, d <=106
0<=ai<=106

输出:

There is only one test case.
First line, four integers, n, b, c, d.
Second line, n integers, a0, …, an-1.

1<=n<=105
1<= b, c, d <=106
0<=ai<=106

样例输入:

2 1 2 3
0 1

样例输出:

4
7

题解转自:http://www.klogk.com/posts/hdu4565/

题意非常简单,a,b,n都是正整数,求

Sn=(a+b)n%m,(a1)2<b<a2

这个题目也是2008年Google
Codejam Round 1A的C题

做法其实非常简单,记(a+b)nAn,配项

Cn=An+Bn=(a+b)n+(ab)n

两项恰好共轭,所以Cn是整数。又根据限制条件

(a1)2<b<a20<ab<10<(ab)n<1Bn<1

也就是说Cn=An

Sn=(Cn)%m

Cn的方法是递推。
Cn乘以(a+b)+(ab)

于是

Cn+1=2aCn(a2b)Cn1

把这个递推式写成矩阵形式

[Cn+1Cn]=[2a1(a2b)0][CnCn1]

于是就可以用矩阵快速幂来做了

[Cn+1Cn]=[2a1(a2b)0]n[C1C0]

—————————————————————————-
以上是原版的题解。
这个题目是我做训练赛的时候做到的,当时没做出来,后来看题解,一开始不明白为什么C[N]=[ A[N]  ];
后来的时候百度了一下共轭的定义发现:
C[N]一定是一个整数。
B[N]又小于1.
所以
C[N]=[ A[N]  ]=A[N]+B[N];
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
#define maxn 3001
#define LL long long
struct matrix
{
    LL mat[3][3];
    matrix()
    {
        memset(mat,0,sizeof(mat));
    }
};
int m;
matrix mul(matrix A,matrix B)
{
    matrix C;
    for(int i=1;i<=2;i++)
    {
        for(int j=1;j<=2;j++)
        {
            C.mat[i][j]=0;
            for(int k=1;k<=2;k++)
            {
                C.mat[i][j]+=A.mat[i][k]*B.mat[k][j];
            }
            C.mat[i][j]%=m;
            if(C.mat[i][j]<0)C.mat[i][j]+=m;
        }
    }
    return C;
}
matrix pows(matrix A,LL p)
{
    matrix B;
    B.mat[1][1]=B.mat[2][2]=1;
    while(p)
    {
        if(p&1)B=mul(B,A);
        A=mul(A,A);
        p>>=1;
    }
    return B;
}
int main()
{
    int a,b,n;
    while(~scanf("%d%d%d%d",&a,&b,&n,&m))
    {
        matrix A;
        A.mat[1][1]=2;
        A.mat[2][1]=2*a;
        matrix B;
        B.mat[1][1]=0;     B.mat[1][2]=1;
        B.mat[2][1]=b-a*a; B.mat[2][2]=2*a;
        B=pows(B,n);
        A=mul(B,A);
        cout<<A.mat[1][1]<<endl;
    }
    return 0;
}






















版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/rowanhaoa/article/details/36460203