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

笔记

矩阵

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

然后就用这个时间来补数学 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

$Fixed$ $Code$：100%

#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 乘起来的积即为答案。

本文作者：Snowflake_Pink
本文链接：https://snowflake.pink/archives/84/
最后修改时间：2020-04-14 09:35:49
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！