【考前冲刺Day3】青春期猪头少年不会取"膜"

发布于 2018-11-05  283 次阅读


T1 海龟

题目大意:给你n个点,依次连接形成一条折线,问这条折线经过了多少个整点真的不是刀剑里的那个海龟

考试的时候写了两个程序,一个是枚举矩阵里的点带进函数,一个是枚举x算出y,后者写挂了,但是对拍的时候考试用的电脑没法用fc,人工对比耗费了不少时间而且还没对比出来,于是把两个程序混合起来只有60分

想法很简单,每次枚举一条线段覆盖的最小矩阵的所有点,带进直线方程看看在不在直线上,用bool数组标记就好了.

正解好像是用gcd模拟

T2 子集

题目大意:求有n个元素的集合里有多少个元素数目不超过k的子集数目,对m取"膜",不保证m是质数

骗我写一发逆元组合数,然而只过了暴力的分..
前40分是杨辉三角递推
后40分是逆元(但是要有技巧的统计答案)
先上80分代码:

我们首先来抽象化一下这道题到底要求什么,显然,其实它就是求一个式子:


\(\displaystyle \sum_{i\in[0,k]} C^i_n mod m\)

我们之前用费马小定理为什么会失败呢?没错,就是m不保证是质数!  
于是我们要用到费马小定理的一般情况的定理-欧拉定理
对于一般的组合式公式我们可以进行以下化简:\(C_n^m=\frac{n!}{m!(n-m)!}=\frac{n(n-1)\cdots (n-m+1)}{m!}\)
由于我们要求的式子n是不变的,所以分子每次可以用上次的分子递推(上面80分的程序也用了这种方法)
而对于我们的正解,我们甚至用ans来保存上一项的答案(可以直接用到当前项)
对于每一个分子,我们将mod的质因子提取出来并计数(加法),剩下来的一定与mod互质,与ans相乘.
对于每一个分母,我们将mod的质因子提取出来并计数(减法),剩下来的一定与mod互质,与ans相除(乘上逆元).
这里的逆元用的是欧拉定理,即\(a^{\varphi(n)}\equiv 1(mod\ n)\),其中a,n互质
我们不能直接将ans统和计入答案,我们还必须讲每个用ans乘上每个质因子才能计入答案统和



哇,你居然发现了这里!