Codeforces 678D Iterated Linear Function

链接

传送门

题意

定义\(f(x)=Ax+B\)、\(g^{(0)}(x)=x\)、\(g^{(n)}(x)=g^{(n-1)}(x)\)。给出\(A\)、\(B\)、\(n\)、\(x\) \((1 \leq A,B,x \leq 10^9,1 \leq n \leq 10^{18})\)，求\(g^{(n)}(x)\)对\(10^9+7\)取模的值。

思路

数据范围和题目形式很显然的就是矩阵题。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const LL mod = 1000000007;
const int maxn = 2;

struct Matrix {
  LL a[maxn][maxn];
  
  Matrix() {
    memset(a, 0, sizeof a);
    for (int i = 0; i < maxn; ++i) {
      a[i][i] = 1;
    }
  }
  
  Matrix operator * (const Matrix& rhs) const {
    Matrix res;
    memset(res.a, 0, sizeof res.a);
    for (int k = 0; k < maxn; ++k) {
      for (int i = 0; i < maxn; ++i) {
        for (int j = 0; j < maxn; ++j) {
          res.a[i][j] = (res.a[i][j] + a[i][k] * rhs.a[k][j]) % mod;
        }
      }
    }
    return res;
  }
};

Matrix pow_mod(Matrix x, LL k) {
  Matrix res, cur = x;
  while (k) {
    if (k & 1) {
      res = res * cur;
    }
    cur = cur * cur;
    k >>= 1;
  }
  return res;
}

int main() {
  LL A, B, n, x;
  scanf("%lld%lld%lld%lld", &A, &B, &n, &x);
  Matrix ans;
  ans.a[0][0] = A, ans.a[0][1] = B;
  ans.a[1][0] = 0, ans.a[1][1] = 1;
  ans = pow_mod(ans, n);
  printf("%lld\n", (ans.a[0][0] * x + ans.a[0][1]) % mod);
  return 0;
}