UVA - 10870 Recurrences 【矩阵快速幂】

题目链接

https://odzkskevi.qnssl.com/d474b5dd1cebae1d617e6c48f5aca598?v=1524578553

题意

给出一个表达式算法 f(n)

思路

n 很大自然想到是矩阵快速幂

那么问题就是怎么构造矩阵

我们想到的一种构造方法是

n = 2 时

n = 3 时

然后大概就能够发现规律了吧。。

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 <list>

#include <numeric>

#include <sstream>

#include <iomanip>

#include <limits>

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

#define pb push_back

#define bug puts("***bug***");

#define fi first

#define se second

#define stack_expand #pragma comment(linker, "/STACK:102400000,102400000")

#define syn_close   ios::sync_with_stdio(false);cin.tie(0);

#define sp system("pause");

//#define bug

//#define gets gets_s

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;

typedef pair <double, int> pdi;

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 + 10;

const int MOD = 142857;

int d, n, m;

ll a[20], b[20];

struct Matrix

{

    ll a[20][20];

    Matrix() {}

    Matrix operator * (Matrix const &b)const

    {

        Matrix res;

        CLR(res.a, 0);

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

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

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

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

        return res;

    }

};

Matrix pow_mod(Matrix ans, int n)

{

    Matrix base;

    CLR(base.a, 0);

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

    {

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

    }

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

    {

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

    }

    while (n > 0)

    {

        if (n & 1)

            ans = ans * base;

        base = base * base;

        n >>= 1;

    }

    return ans;

}

int main()

{

    while (scanf("%d %d %d", &d, &n, &m) && (d || n || m))

    {

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

            scanf("%lld", &a[i]);

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

            scanf("%lld", &b[i]);

        if (n <= d)

        {

            printf("%lld\n", b[n - 1] % m);

            continue;

        }

        Matrix ans;

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

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

                ans.a[i][j] = b[d - j - 1];

        ans = pow_mod(ans, n - d);

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

    }

    return 0;

}

巴特西

UVA - 10870 Recurrences 【矩阵快速幂】

最新文章

热门文章