Iterated Linear Function 매트릭스 빠른 멱

Consider a linear function f(x) = Ax + B. Let’s define g(0)(x) = x and g(n)(x) = f(g(n - 1)(x)) for n > 0. For the given integer values A, B, n and x find the value of g(n)(x) modulo 109 + 7.
Input The only line contains four integers A, B, n and x (1 ≤ A, B, x ≤ 109, 1 ≤ n ≤ 1018) — the parameters from the problem statement.
Note that the given value n can be too large, so you should use 64-bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.
Output Print the only integer s — the value g(n)(x) modulo 109 + 7.
직접 빠른 멱이면 되는데 갑자기 자신의 블로그에 매트릭스 빠른 멱이 하나도 없다는 것을 발견하고 밀어낸다.[a,b,0,1]^n* [x,0,1,0]
ll과 초기화...각자 한 발씩.괴롭다

#include
#include
#include
#define _for(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll a, b, n, x;
struct mat {
    ll m[2][2];
};
mat temp = {{1, 0, 0, 1}};
mat muti(mat a, mat b) {
    mat ans;
    memset(ans.m, 0, sizeof(ans.m));
    for(ll i = 0; i < 2; i++) {
        for(ll j = 0; j < 2; j++) {
            ans.m[i][j] = 0;
            for(ll k = 0; k < 2; k++) {
                ans.m[i][j] = (ans.m[i][j] % mod + a.m[i][k] * b.m[k][j] % mod) % mod;
            }
        }
    }
    return ans;
}
mat mquick(ll xxx) {
    mat ans = temp;
    mat temp2 = {{a, b, 0, 1}};
    while(xxx) {
        if(xxx & 1)
            ans = muti(ans, temp2);
        temp2 = muti(temp2, temp2);
        xxx >>= 1;
    }
    return ans;
}
int main() {
    while(~scanf("%lld %lld %lld %lld", &a, &b, &n, &x)) {
        mat fuck = {{x, 0, 1, 0}};
        fuck = muti(mquick(n), fuck);
        printf("%lld
", (fuck.m[0][0] % mod + mod) % mod);
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[HDU 5608] function

Problem Description There is a function f(x),which is defined on the natural numbers set N,satisfies the following eqaut...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

Iterated Linear Function 매트릭스 빠른 멱

좋은 웹페이지 즐겨찾기