【数学】专项训练（施工中） 2021-07-14 学习,题解,笔记,算法与数据结构 1 条评论 122 次阅读 # math [TOC] ## 1 复数，位运算，快速幂，欧几里得算法 之所以在第一次训练时大量选用了洛谷的题，主要是因为~~它有自动推荐的功能~~它是中文题面，还集成了题解，适合测试板子。十分友好，适合新手入门。由于我们的 VJ 暂不支持洛谷，所以请自己注册洛谷账号并，到时会手动记录做题情况。 除此之外，大量的题目都非常友好，主要是锻炼~~英文读题能力~~同学们的手速，加强对数学的兴趣，培养出选数学专题的信心。 如果思考了一小时还毫无头绪，建议先换一题。如果思考了一天还不大行，建议搜搜题解。如果问了一圈还有点小困难，可以来问我。问之前请先浏览一遍[提问的智慧](https://github.com/tvvocold/How-To-Ask-Questions-The-Smart-Way)。 除了 `HAOI2008]圆上的整点` 该题，其它要求 AK。 1. [洛谷](https://www.luogu.com.cn/) * [x] [[HAOI2008]圆上的整点](https://www.luogu.com.cn/problem/P2508) * [x] [[NOIP2003 普及组] 麦森数](https://www.luogu.com.cn/problem/P1045) * [x] [[NOIP2012 提高组] 同余方程](https://www.luogu.com.cn/problem/P1082) * [x] [有理数取余](https://www.luogu.com.cn/problem/P2613) * [x] [裴蜀定理](https://www.luogu.com.cn/problem/P4549) * [x] [二元一次不定方程](https://www.luogu.com.cn/problem/P5656) * [x] [青蛙的约会](https://www.luogu.com.cn/problem/P1516) * [x] [斐波那契数列](https://www.luogu.com.cn/problem/P1962) * [x] [广义斐波那契数列](https://www.luogu.com.cn/problem/P1349) * [x] [矩阵加速（数列）](https://www.luogu.com.cn/problem/P1939) * [x] [【模板】矩阵快速幂](https://www.luogu.com.cn/problem/P3390) 2. [CrossFire](https://codeforces.com/) * [x] 7C Line * [x] 45G Prime Problem * [x] 1010C Border * [x] 983A Finite or not? * [ ] 27E * [ ] 17D 3. [HDU](https://vjudge.net) * [x] 5950 Recursive sequence * [x] 2582 f(n) * [x] 1576 A/B * [ ] 5144 4. [POJ](http://poj.org) * [ ] 3126 * [ ] 2909 * [ ] 2689 * [ ] 1811 * [ ] 2429 * [ ] 2407 * [ ] 2773 * [ ] 2478 * [ ] 3090 * [ ] 3358 * [ ] 2992 * [ ] 2480 * [ ] 1845 5. [SPOJ](https://www.spoj.com/) 可以去 [VJ](https://vjudge.net/) 写。 * [x] 3442 LASTDIG - The last digit * [ ] 2906 GCD2 - GCD2 * [ ] 31 MUL - Fast Multiplication * [x] SPOJ-14329 LOCKER - Magic of the locker * [x] SPOJ-9494 ZSUM - Just Add It 6. [UVA](https://onlinejudge.org/) * [x] 374 Big Mod * [x] 11029 Leading and Trailing * [x] 1230 MODEX * [x] 10104 Euclid Problem * [x] 11827 Maximum GCD * [x] 11417 GCD * [x] 12775 Gift Dilemma * [ ] 495 Fibonacci Freeze * [ ] 10083 Division 7. [Gym](https://codeforces.com/gyms) * [ ] 100963J Once Upon A Time 8. Exam * [x] HDU-2157 How many ways?? * [x] HDU-1005 Number Sequence * [x] HDU-5015 233 Matrix * [x] CF-23B Party * [x] CF-75C Modified GCD * [x] CF-630I Parking Lot * [x] HDU 6961 I love cube * [x] HDU 6950 Mod, Or and Everything 一两道纯粹的模板题，三四道签到水题，一两道简单的思维题，两三道中等难度的题。 信心增强测试。除去模板，平均代码量大概一二十行。这么短的代码，故赛后要求全补了。希望大佬们纷纷 AK。 总共~~八~~~~六~~八题。 9. 讲题与其它 我挑了一些个人觉得可能有点思考量的题目，最后一天上午来讲下题吧。 如果还想听或讲其它题目的，欢迎私聊我。 自愿报名的，评分可以加点分:smirk:如果人数不够就随机抓两个。 ~~练习题过题数小于 60% 的，差不多 20 题，除非考试时发挥了真正的实力，不然评分可能有点小低~~ 最后来填份 **[问卷]** 吧。 | Origin | Title | | :--------------: | :--------------------------: | | CodeForces 45G | B - Prime Problem | | CodeForces 1010C | C - Border | | CodeForces 983A | D - Finite or not? | | UVA 11029 | F - Leading and Trailing | | UVA12775 | K - Gift Dilemm | | SP14329 | LOCKER - Magic of the locker | | HDU 5950 | A - Recursive sequence | | HDU 2582 | B - f(n) | ## 2 组合，容斥 1. 题目 * [ ] HDU 2. Exam * [ ] HDU 6961 I love cube 似曾相识燕归来 * [ ] HDU 3037 Saving Beans 年年岁岁花相似 * [ ] HDU 1808 Halloween treats 抽刀断水水更流 * [ ] HDU 6143 Killer Names 拔剑四顾心茫然 * [ ] CF57C Array 不经一番寒彻骨 * [ ] CF451E Devu and Flowers 此心安处是吾乡 ### 题解 下次测试不会出现任何本专题里出现过的原题。 1. HDU 6961 I love cube 似曾相识燕归来 测试一原题。 为啥过得这么慢。 2. HDU 3037 Saving Beans 年年岁岁花相似 Lucas 定理板子题。 答案为。 3. HDU 1808 Halloween treats 抽刀断水水更流 抽屉原理板子题。 因为题目中保证$$C \le N$$，所以一定存在一个连续的区间，满足题目要求。请读者自证。 4. HDU 6143 Killer Names 拔剑四顾心茫然 交给一血选手完成。 容斥或第二类斯特林数都可做。 ~~凌晨传错题了，不好意思，本来放的是 CF1342E Placing Rooks~~ 5. CF57C Array 不经一番寒彻骨 ~~可以打表找规律~~ 不增不降对称，先考虑不降。 考虑一个$$1 \times (2n-1)$$的矩阵，其中$$n-1$$是空格，其它的$$n$$块是数字，表示从第一格到当前格共出现过多少空格，可以发现该矩阵的数字满足题目要求。 譬如$$n=4,[0,1,1,3]$$可以表示如下矩阵：  这样的序列有$$C_{2n-1}^{n}$$个。 当数组中$$n$$个数都相同的话，重复了$$2$$次，共$$n$$种。 答案$$2C_{2n-1}^{n}-n$$。 6. CF451E Devu and Flowers 此心安处是吾乡 多重集的组合数加容斥原理。 有 $$s$$个球，$$n$$个盒子，第 $$i$$个盒子最多能放$$f_i$$个球，也可以不放，问放球的方案总数。 求方程 $$x_1+x_2+x_3+\cdots+x_n=r$$，且满足 $$x_i\leq f_i$$的约束条件的非负整数解数。 如果没有限制，答案是$$C_{s+n-1}^{n-1}$$。 现考虑不符合题意的方案数。由于$$n$$较小，直接枚举子集，根据子集元素个数的奇偶性进行容斥。 对于任意$$i\in S$$都满足 $$x_i>f_i$$，设$$y_i = x_i - (f_i + 1)[i \in S]$$，可以转化问题为求$$y_1 + y_2+ \cdots + y_n = S-\sum_{i \in S}(f_i + 1)$$。 ## 3 数论 1. Problem * [ ] 2. Exam * [x] HDU 7046 模拟只会猜题意 注意格式 * [x] HDU 5446 贪心只能过样例 注意范围 * [x] CF 803F 数学上来先打表 注意读题 * [x] CF 1342E 组合数学碰运气 注意补题 * [x] CF 1208G 计算几何瞎暴力 注意特判 * [ ] 数论只会 GCD 注意跟榜 ### Solution 本来这次的最后一题是舟巨出的贼牛批的原创题，可惜放不上来，等下次吧。 1. HDU 7046 模拟只会猜题意 注意输出 数列求和公式。 2. HDU 5446 贪心只能过样例 注意范围 中国剩余定理。 用卢卡斯定理算出单独的每一个素数下的值，可以得到一个一元线性同余方程组。再用中国剩余定理一解就行。 3. CF 803F 数学上来先打表 注意读题 莫比乌斯函数~~，可以用 dp 做~~。 枚举 gcd，然后容斥。 答案显然是 $$2^n-1$$ 减去 $$gcd>1$$ 的子序列个数 $$2^{f_i}-1$$。然后枚举一下包含因子的数的个数，而它在容斥下的系数（奇减偶加的形式）就是$$\mu(x)$$。 莫比乌斯函数本身就是一个容斥的映射。 4. CF 1342E 组合数学碰运气 注意特判 第二类斯特林数~~，有生成函数的解法~~。 由于所有格子都需要被车在一步内攻击到，因此该棋盘每一行或者每一列都至少有一个车。 由于车不能跨过棋子攻击，因此最多存在$$k-1$$对车能够互相攻击。 将这 $$n$$个车看作图上的点，在能够互相攻击的车之间连线，一共需要连 $$k$$条线，因此相当于 $$n$$-k 个连通分量，问题转化为将 $$n$$个元素划分为$$ n−k $$个子集有几种方法。 由于只有$$n−k$$ 列中有车，且是无序的，行列不等，故答案为$$2S_n^{n−k}C_n^{n−k}(n−k)!$$。 5. CF 1208G 计算几何瞎暴力 注意特判 欧拉函数。 显然，选择正$$n$$边形时，一定也会选择满足$$m|n$$的正$$m$$边形。 答案就是前$$k$$个最小的$$\phi(n)$$的累加和。 ## 4 线性代数 ## 5 杂项 标签: none CC0
阿巴阿巴