T1 海龟

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

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

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

正解好像是用ｇｃｄ模拟

T2 子集

题目大意：求有ｎ个元素的集合里有多少个元素数目不超过ｋ的子集数目，对ｍ取＂膜＂，不保证ｍ是质数

骗我写一发逆元组合数，然而只过了暴力的分．．
前４０分是杨辉三角递推
后４０分是逆元（但是要有技巧的统计答案）
先上８０分代码：

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

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

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

---