HDU - 4990 Reading comprehension 【矩阵快速幂】

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=4990

题意

初始的ans = 0

给出 n, m

for i in 1 -> n

如果 i 为奇数

ans = (ans * 2 + 1) % m

反之

ans = ans * 2 % m

思路

如果我们只计算偶数项那么递推公式就是

ans[n] = 4 * ans[n - 2] + 2

如果 n 是偶数那么刚好就按这个公式推第 n / 2 项

如果 n 是奇数那么就是第【 n / 2 项】 * 2 + 1

可以推知的矩阵为

然后矩阵快速幂

AC代码

#include <cstdio>

#include <cstring>

#include <ctype.h>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <map>

#include <stack>

#include <set>

#include <numeric>

#include <sstream>

#include <iomanip>

#include <limits>

#define CLR(a, b) memset(a, (b), sizeof(a))

#define pb push_back

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

typedef pair<string, int> psi;

typedef pair<string, string> pss;

const double PI = acos(-1.0);

const double E = exp(1.0);

const double eps = 1e-8;

const int INF = 0x3f3f3f3f;

const int maxn = 1e2 + 5;

//const int MOD = 1e4;

int MOD;

struct Matrix

{

    ll a[2][2];

    Matrix () {}

    Matrix operator * (Matrix const &b)const

    {

        Matrix res;

        CLR(res.a, 0);

        for (int i = 0; i < 2; i++)

            for (int j = 0; j < 2; j++)

                for (int k = 0; k < 2; k++)

                    res.a[i][j] = (res.a[i][j] + this->a[i][k]  * b.a[k][j]) % MOD;

        return res;

    }

};

Matrix pow_mod(Matrix base, int n)

{

    Matrix ans;

    CLR(ans.a, 0);

    ans.a[0][1] = 1;

    while (n > 0)

    {

        if (n & 1)

            ans = ans * base;

        base = base * base;

        n >>= 1;

    }

    return ans;

}

int main()

{

    Matrix base;

    base.a[0][0] = 4;

    base.a[0][1] = 0;

    base.a[1][0] = 2;

    base.a[1][1] = 1;

    int n;

    while (~scanf("%d%d", &n, &MOD))

    {

        Matrix ans = pow_mod(base, n / 2);

        if (n & 1)

            printf("%lld\n", (ans.a[0][0] * 2 + 1) % MOD);

        else

            printf("%lld\n", ans.a[0][0] % MOD);

    }

}

巴特西

HDU - 4990 Reading comprehension 【矩阵快速幂】

最新文章

热门文章