louhc

分类

未归档(78) 题解(81)

/ 注册

全部文章（共160篇）

题解|信息学奥赛一本通-提高篇 Fibonacci第n项

思路矩阵加速递推基础题.因为,可以构造出矩阵. 然后跑矩阵快速幂即可.矩阵构造方法很多,怎么构造开心就好.注意一些小细节,因为可能是,最后输出是也最好取模一下.平时写矩阵就注意下常数优化.毕竟矩阵乘法的常数还是比较大的. 代码 #include<bits/stdc++.h> using...

斐波那契数列矩阵乘法快速幂

2019-08-20

0 611

题解 | 信息学奥赛一本通-提高篇矩阵 A×B

思路很基本的矩阵乘法.直接根据矩阵乘法的定义暴力求解即可.别忘了开long long. 复杂度为.事实上还有一种更优秀的做法Strassen可以把复杂度优化到.不过话说回来一般不会遇到这么毒瘤的出题人来卡你,感兴趣的童鞋可以去网上查找资料. 代码 #include<bits/stdc++.h...

矩阵乘法

2019-08-20

0 611

题解 | 算法竞赛进阶指南 Zap

思路题意是求莫比乌斯反演最重要的当然就是推柿子.假设,不满足的话swap一下就OK了这就是一个用数论分块可以解决的东西.只要预处理一下前缀和就OK了.数论分块一次的复杂度为,因此总复杂度为.因为不是很卡常数所以没有优化除法....至于如何优化除法可以参考https://www.luogu...

莫比乌斯反演数论分块积性函数

2019-08-19

0 617

题解 | 算法竞赛进阶指南 a^b

思路基本的快速幂.首先我们知道.因此求时对进行二进制拆分.也就是将写成的形式.其中表示位与,中的为真时值为1,否则为0.然后就变成了.因为一个范围内的正整数二进制下最多只有位,所以只要进行次运算就可以算出结果.接下来是大家喜闻乐见的代码. 代码 #include<bits/stdc++....

快速幂二进制拆分

2019-08-19

0 514

「UVA1185」Big Number 解题报告

UVA1185 Big Number In many applications very large integers numbers are required. Some of these applications are using keys for secure transmission o...

2019-01-21

0 631

「洛谷P3202」[HNOI2010]弹飞绵羊解题报告

P3203 [HNOI2010]弹飞绵羊题目描述某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到...

2019-01-21

0 460

「洛谷P2906」[USACO08OPEN]牛的街区Cow Neighborhoods 解题报告

P2906 [USACO08OPEN]牛的街区Cow Neighborhoods 题目描述 Those Who Know About Cows are aware of the way cows group into 'Cow Neighborhoods'. They have observed...

2019-01-19

0 693

「洛谷P1306」斐波那契公约数解题报告

P1306 斐波那契公约数题目描述对于Fibonacci数列：1,1,2,3,5,8,13......大家应该很熟悉吧~~~但是现在有一个很“简单”问题：第n项和第m项的最大公约数是多少？输入输出格式输入格式：两个正整数n和m。（n,m<=10^9）注意：数据很大输出...

2019-01-18

0 529

「SP25784」BUBBLESORT - Bubble Sort 解题报告

SP25784 BUBBLESORT - Bubble Sort 题目描述 One of the simplest sorting algorithms, the Bubble Sort, can be expressed as (0-based array): procedure bubbl...

2019-01-15

0 936

「UVA12004」 Bubble Sort 解题报告

UVA12004 Bubble Sort Check the following code which counts the number of swaps of bubble sort. int findSwaps( int n, int a[] ) { int count = 0, ...

2019-01-15

0 603