2019.8.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 的数列” 有点像,但是还是差了很多。

令:

然后 通过比较 (数学一本通上的话相当精辟),得出一个矩阵 $A$ ,使得 $F’ = A \times F$:

然后就有:


怎么推出这个矩阵的啊 QAQ

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

玄学复杂度…..

我也不会去学的……

考试

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

库特的向量

直接贪心….

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

$Fixed$ $Code$:100%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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!}$ 。

推导过程:

因为,

所以,

令,

则,

然后问题就转化为:在 $(n!)^2$ 有多少个正整数因子,所以分解一下质因数,然后各个指数 $+$ 1 乘起来的积即为答案。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×