HDU 6395 – Sequence (分块+快速幂)

题意

计算$F_n \mod 10^9+7$,定义如下:$$\begin{cases} F_1 &=& A \\ F_2 &=& B \\ F_n &=& C\cdot{}F_{n-2}+D\cdot{}F_{n-1}+\left\lfloor\frac{P}{n}\right\rfloor \end{cases}$$

数据范围

  • $1 \leq T \leq 20$
  • $0 \leq A, B, C, D \leq 10^9$
  • $1 \leq P, n \leq 10^9$

思路

这题太硬核了我脑子里只有$O(n)$的算法肯定跑不过嘛

如果$\left\lfloor\frac{P}{n}\right\rfloor$的值是固定的那么肯定可以快速幂解决了,但是难就难在这个值会随着$n$变化。聪明的徐臣发现了当$n$很大的时候,这个值几乎是不变的,有很长一段区间可以用快速幂解决。

那么$n$多大的时候这样计算才不会浪费呢?其实根本不会浪费因为快速幂肯定跑的快啊!

对于开始值$i$,这一段快速幂计算区间为$\left[ i, P / (P / i) \right]$(注意除法会消掉余数,所以右端点正好是保持$\lfloor\frac{P}{N}\rfloor$值不变的最大值)。用矩阵快速幂疯狂向前推就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll modulo = (ll) 1e9 + 7;

class matrix{
 public:
  ll s[3][3];

  matrix(){
    memset(s, 0, sizeof(s));
  }
  matrix(ll Fn, ll Fn1, ll E) {
    s[0][0] = Fn;
    s[0][1] = Fn1;
    s[0][2] = E;
    s[1][0] = s[1][1] = s[1][2] = 0;
    s[2][0] = s[2][1] = s[2][2] = 0;
  }
  matrix(ll C, ll D) {
    s[0][0] = D;
    s[1][0] = C;
    s[0][1] = s[2][0] = s[2][2] = 1;
    s[0][2] = s[1][1] = s[1][2] = s[2][1] = 0;
  }
};

matrix mul(matrix &a, matrix &b) {
  matrix ret;
  for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < 3; ++j) {
      for (int k = 0; k < 3; ++k) {
        ret.s[i][j] = (ret.s[i][j] + a.s[i][k] * b.s[k][j]) % modulo;
      }
    }
  }
  return ret;
}

ll A = 0, B = 0, C = 0, D = 0, P = 0, n = 0;

void xmul(ll &Fn, ll &Fn1, ll E, ll t) {
  matrix ret(Fn, Fn1, E);
  matrix b(C, D);
  while (t) {
    if (t & 1) {
      ret = mul(ret, b);
    }
    b = mul(b, b);
    t >>= 1;
  }
  Fn = ret.s[0][0];
  Fn1 = ret.s[0][1];
}

ll solve() {
  if (n == 1) return A;
  if (n == 2) return B;
  ll Fn1 = A, Fn = B, nex = 0, PN = 0;
  matrix res;
  for (ll i = 3; i <= n; ) {
    PN = P / i;
    if (PN == 0) {
      nex = n;
    } else {
      nex = min(n, P / PN);
    }
    xmul(Fn, Fn1, PN, nex - i + 1);
    i = nex + 1;
  }
  return Fn;
}

int main() {
  int T = 0;
  scanf("%d", &T);
  while (T--) {
    scanf("%lld%lld%lld%lld%lld%lld", &A, &B, &C, &D, &P, &n);
    printf("%lld\n", solve());
  }
}

NowCoder 202A – 矩阵乘法 (分块)

呜呜呜这才第三道水题我就不会做了。

题意

给你$N \times P$和$P \times M$的两个矩阵A与B,其中B是二进制矩阵。求$A \times B$的所有元素的异或和。

数据范围

  • $2 \le N, M \le 2048$
  • $1 \le P \le 64$
  • $0 \le A_{ij} \le 65536$

思路

呜呜呜这数据范围这么大做屁啊!如果直接计算$C$的话需要$2^{48} $次运算怎么可能跑得过啊

想想异或运算有没有什么特别的,没有

STFW看看有没有什么快速算矩阵的方法,没有

群里问大佬,大佬说的听不懂,僵

然后Bing搜了个原题出来……

简单地说就是预处理这个矩阵来使得乘法运算的次数大幅度减少,那么在$O(NPM)$的复杂度下能够卡过去。怎么处理呢?考虑到$B$是一个二进制矩阵,$A_i$与$B_j$的相乘的结果代表$A_i$中对应列元素的和。如果直接预处理需要考虑$2^{64}$种和的情况,根本不行。

然后就可以用神奇的分块了,每$\sqrt{P} = 8$个$A_{ij}$分为一块,那么只需要处理$2^{10} \times 8 \times 2^8 = 2 \times 10^6$种和就可以了。对于每一个$C_{ij}$,只需要对对应的分块和进行至多8次加法即可求出。

总时间复杂度为$$O(N \times P \times2^8)+O(MP)+O(NM\sqrt{P})+O(NM).$$

代码

#include <bits/stdc++.h>
using namespace std;

int n = 0, p = 0, m = 0, bk = 0;
int a[4200][70] = {};
int b[4200][70] = {};
int c[4200][4200] = {};
int apre[4200][10][260] = {};
int bpre[4200][10] = {};
char s[100] = {};

void pre() {
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < bk; ++j) {
      for (int k = 0; k < 256; ++k) {
        for (int p = 0; p < 8; ++p) {
          if ((k >> p) & 1) {
            apre[i][j][k] += a[i][(j << 3) + p];
          }
        }
      }
    }
  }
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < bk; ++j) {
      for (int p = 0; p < 8; ++p) {
        bpre[i][j] += b[i][(j << 3) + p] << p;
      }
    }
  }
}

int getAns() {
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      for (int p = 0; p < bk; ++p) {
        c[i][j] += apre[i][p][bpre[j][p]];
      }
    }
  }

  int ans = 0;
  for (int i = 0; i < n; ++i) {
    for (int j= 0; j < m; ++j) {
      ans ^= c[i][j];
    }
  }
  return ans;
}

int main() {
  scanf("%d%d%d", &n, &p, &m), bk = ((p - 1) >> 3) + 1;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < p; ++j) {
      scanf("%x", &a[i][j]);
    }
  }
  for (int i = 0; i < m; ++i) {
    scanf("%s", s);
    for (int j = 0; j < p; ++j) {
      b[i][j] = s[j] - '0';
    }
  }
  pre();
  printf("%d\n", getAns());
  return 0;
}