20200617 SCOI模拟T2（高精度）（矩陣快速幂）（數學問題）

T2 P4461 [CQOI2018]九連環

思路：

先推式子

發現對于 i 連環，必定先取下第 i 個

11 … … 1 − > 01 … … 1 11……1->01……1 11……1−>01……1

考慮過程

111 … … 1 − > 110 … … 0 − > 010 … … 0 − > 011 … … 1 111……1\\ ->110……0\\ ->010……0\\ ->011……1 111……1−>110……0−>010……0−>011……1

設 f [ i ] f[i] f[i] 為 i 連環全部取下所用步數

有轉移方程

f [ i ] = f [ i − 1 ] + 2 × f [ i − 2 ] + 1 f[i]=f[i-1]+2\times f[i-2]+1 f[i]=f[i−1]+2×f[i−2]+1

遞推求通項

f [ i ] = ⌊ 2 i + 1 3 ⌋ f[i]=\lfloor \frac{2^{i+1}}{3} \rfloor f[i]=⌊32i+1​⌋

可以矩陣快速幂

于是就……A了

一看資料範圍，發現不對

需要高精

黑科技：壓位高精

就是用一位數組存下多位十進制

一般對 1 e 9 1e9 1e9 取模（相乘不會爆 longlong）

代碼：

#include <bits/stdc++.h>
using namespace std;
#define in Read()
#define LL long long

inline char ch() {
  static char buf[1 << 21], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++;
}

inline int in {
  int s = 0, f = 1;
  char x;
  for (x = ch(); x < '0' || x > '9'; x = ch())
    if (x == '-') f = -1;
  for (; x >= '0' && x <= '9'; x = ch()) s = (s * 10) + (x & 15);
  return f == 1 ? s : -s;
}

const int A = 1e5 + 5;
const LL mod = 1e9;
int m, n;
struct S {
  int a[A], len;
  S() { memset(a, 0, sizeof(a)); }
  inline S friend operator*(const S u, const S v) {
    S w;
    LL now = 0;
    for (int i = 1; i <= u.len; i++) {
      now = 0;
      for (int j = 1; j <= v.len; j++) {
        now += 1ll*u.a[i] * v.a[j] + 1ll*w.a[i + j - 1];
        w.a[i + j - 1] = now % mod;
        now /= mod;
      }
      if (now) w.a[i + v.len] = now;
    }
    w.len = u.len + v.len - 1;
    if (w.a[u.len + v.len]) w.len++;
    return w;
  }
  inline S friend operator/(const S u, LL v) {
    S w;
    LL now = 0;
    for (int i = u.len; i; i--) {
      now = 1ll*now * mod + 1ll*u.a[i];
      w.a[i] = 1ll*now / v;
      now %= v;
    }
    w.len = u.len;
    if (!w.a[u.len]) w.len--;
    return w;
  }
} u, v;

inline void print(S u) {
  S x = u;
  printf("%d", x.a[x.len]);
  for (int i = x.len - 1; i; i--) {
    for (int j = mod / 10; j; j /= 10) {
      printf("%d", x.a[i] / j);
      x.a[i] %= j;
    }
  }
  printf("\n");
  return;
}

inline S power(S u, LL c) {
  v.a[1] = 1, v.len = 1;
  while (c) {
    if (c & 1) v = v * u;
    u = u * u;
    c >>= 1;
  }
  return v;
}

signed main() {
  m = in;
  while (m--) {
    n = in;
    n++;
    u.a[1] = 2, u.len = 1;
    u = power(u, n);
    u = u / 3;
    print(u);
  }
  return 0;
}