math

[TOC]

1 复数，位运算，快速幂，欧几里得算法

之所以在第一次训练时大量选用了洛谷的题，主要是因为它有自动推荐的功能它是中文题面，还集成了题解，适合测试板子。十分友好，适合新手入门。由于我们的 VJ 暂不支持洛谷，所以请自己注册洛谷账号并，到时会手动记录做题情况。

除此之外，大量的题目都非常友好，主要是锻炼英文读题能力同学们的手速，加强对数学的兴趣，培养出选数学专题的信心。

如果思考了一小时还毫无头绪，建议先换一题。如果思考了一天还不大行，建议搜搜题解。如果问了一圈还有点小困难，可以来问我。问之前请先浏览一遍提问的智慧。

除了 HAOI2008]圆上的整点 该题，其它要求 AK。

  1. 洛谷

  2. CrossFire

    • [x] 7C Line
    • [x] 45G Prime Problem
    • [x] 1010C Border
    • [x] 983A Finite or not?
    • [ ] 27E
    • [ ] 17D

  3. HDU

    • [x] 5950 Recursive sequence
    • [x] 2582 f(n)
    • [x] 1576 A/B
    • [ ] 5144

  4. POJ

    • [ ] 3126
    • [ ] 2909
    • [ ] 2689
    • [ ] 1811
    • [ ] 2429
    • [ ] 2407
    • [ ] 2773
    • [ ] 2478
    • [ ] 3090
    • [ ] 3358
    • [ ] 2992
    • [ ] 2480
    • [ ] 1845

  5. SPOJ

    可以去 VJ 写。

    • [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

    • [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

    • [ ] 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 题，除非考试时发挥了真正的实力，不然评分可能有点小低

    最后来填份 [问卷] 吧。

OriginTitle
CodeForces 45GB - Prime Problem
CodeForces 1010CC - Border
CodeForces 983AD - Finite or not?
UVA 11029F - Leading and Trailing
UVA12775K - Gift Dilemm
SP14329LOCKER - Magic of the locker
HDU 5950A - Recursive sequence
HDU 2582B - 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 杂项

文章目录