2019.8.15 集训解题报告
浏览 266 | 评论 0 | 字数 2237
Snowflake_Pink
2019年08月15日
  • 今天好像考数学......


    笔记

    矩阵

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

    然后就用这个时间来补数学 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 授权协议,转载请注明来源,谢谢!
    评论
    评论会由可爱的 AI 来审核鸭~
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论