louhc

题解

未归档(78)

/ 注册

全部文章 / 题解（共5篇）

题解 | 信息学奥赛一本通车的放置

题解枚举上半部分与下半部分分别有多少车.设上半部分有个车,那么上半部分方案数为.下半部分少了几列可以放,方案数为.然后根据乘法原理,乘起来即可.复杂度为.(如果求逆元直接使用快速幂就是,而如果求出最后一个逆元,逆推回去就是,下面直接使用前者) 代码 #include<bits/stdc++....

排列组合

2019-09-01

1 585

题解 | 信息学奥赛一本通超能粒子炮·改

思路设,答案就是.根据卢卡斯定理,我们可以化简上面的式子.也就是.整理一下.递归就OK了.复杂度大概是(至于怎么分析,上面那个式子只有两个部分的变量有可能大于能递归下去). 代码 #include<bits/stdc++.h> using namespace std; #define ...

卢卡斯定理排列组合

2019-09-01

0 722

题解 | 信息学奥赛一本通序列统计

思路不降的话先改成严格上升,也就是第个数加上,范围就是.然后长度为的序列个数为(选任n个,然后排序,第i项减i还原成不降序列).总答案就是,也就是.用卢卡斯定理求解即可.复杂度. 代码 #include<bits/stdc++.h> using namespace std; #defi...

排列组合

2019-09-01

0 698

题解 | 信息学奥赛一本通数三角形

思路选任意不同的三个点方案数为.然后需要减去共线的三个点的方案数.首先横纵方向.然后考虑枚举每个向量(也就是斜率和长度相同的线段同时枚举),该向量起始位置和中间的某个点为一种方案,那么对于向量,贡献为.上下翻转也是可行的,贡献再乘2.这样子复杂度就是. 代码 #include<bits/st...

排列组合

2019-09-01

0 645

题解 | 算法竞赛进阶指南杰拉尔德和巨型象棋

思路因为较大,不能直接用和设计状态.将染成黑色,题目变成求从开始,第一个经过的黑色格子是的路径有多少.先将所有点排序,第一关键字为所在行,第二关键字为所在列.设为从开始,第一个经过的黑色格子为的路径条数.首先,.假设之前不经过任何黑格子,那么.然后减去之前经过黑色格子的路径.枚举这些路径经过的第二...

计数类动态规划动态规划排列组合

2019-08-25

0 603