今天好像考数学......

笔记

矩阵

今天好像考数学，但是我太菜了，就不想考了.....

然后就用这个时间来补数学 qwq

普通递推数列

题面

给出一个 $k$ 阶齐次递推数列 $\{f_i \}$ 的通项公式 $f_i = a_1 \times f_{i - 1} + a_2 \times f_{i - 2} + ... +a_k \times f_{i - k}(i \geq k)$ ，求 $f_n$ 。

分析

这和上次考试的 “小 L 的数列” 有点像，但是还是差了很多。

令： $$ F = \begin{bmatrix} f{i - 1} \ f{i - 2} \ \vdots \ f{i - k}\end{bmatrix},F' = \begin{bmatrix} f_i \ f{i - 1} \ \vdots \ f{i - k + 1}\end{bmatrix} $$ 然后 通过比较 （数学一本通上的话相当精辟），得出一个矩阵 $A$ ，使得 $F' = A \times F$： $$ A = \begin{bmatrix} a_1 & a_2 & a_3 & \cdots & a_k \ 1 & 0 & 0 & \cdots & 0 \ 0 & 1 & 0 & \cdots & 0 \\vdots & \vdots & \vdots & \ddots & \vdots \ 0 & 0 & \cdots & 1 & 0\end{bmatrix} $$ 然后就有： $$ F_i = A^i \times F_0 = \begin{bmatrix} f{i + k - 1} \ f_{i + k - 2} \ \vdots \ f_i \end{bmatrix} $$

怎么推出这个矩阵的啊 QAQ

有一个算法叫做 $Strassen$ 算法，可以把这题的复杂度从 $O(k^3 \log_2 n)$ 降到 $O(k^{2.81} log_2 n)$ ？！

玄学复杂度.....

我也不会去学的......

考试

今天的第一题竟然水得一逼......

库特的向量

直接贪心....

一个从小到大排序，另一个从大到小排序，然后依次对应的取他们的积 QAQ

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
const int MAXN = 1e3 + 5;

long long n, a[MAXN], b[MAXN], ans;

bool cmp (long long a, long long b) {
    return a > b;
}

int main() {
    scanf ("%lld", &n);
    for (int i = 1; i <= n; i++) {
        scanf ("%lld", &a[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf ("%lld", &b[i]);
    }
    
    sort (a + 1, a + n + 1);
    sort (b + 1, b + n + 1, cmp);
    
    for (int i = 1; i <= n; i++) {
        ans += a[i] * b[i];
    }
    
    printf ("%lld\n", ans);
    return 0;
}

恭介的法则

一道数学题，题目要求，在正整数集合中，有多少对 $(x,y)$ 使得 $\frac{1}{x} + \frac{1}{y} = \frac{1}{n!}$ 。

推导过程： $$ \begin{aligned} \frac{1}{x} + \frac{1}{y} &= \frac{1}{n!} \ \frac{x + y}{xy} &= \frac{1}{n!} \ xy &= x \cdot n! + y \cdot n! \ y &= \frac{x \cdot n!}{x - n!} \ \end{aligned} $$ 因为， $$ x,y,n! > 0 $$ 所以， $$ x - n! > 0 $$ 令, $$ x = n! + a(a>0) $$ 则， $$ \begin{aligned} y &= \frac{(n!)^2 + a \cdot n!}{a} \ y &= n! + \frac{(n!)^2}{a} \end{aligned} $$ 然后问题就转化为：在 $(n!)^2$ 有多少个正整数因子，所以分解一下质因数，然后各个指数 $+$ 1 乘起来的积即为答案。