本来应该跟着lf上概率入门但是不知道为什么还是可以在新高二这边苟，于是又听了一节课。讲了大概数学的一些题目，结果我一道都没有见过。。。
Chocolate
题目大意
你有一个口袋，里面有无限个巧克力，有 (c) 种颜色，每次拿出一个（拿出的每种颜色的概率相同）放在桌子上，如果桌子上有该颜色，则拿走桌上另一颜色相同的巧克力，否则将该巧克力放到桌上。求拿出 (n) 个巧克力之后桌上有 (m) 个巧克力的概率。
(cle 100 n,mle 10^6)
思路
很显然的结论就是桌上一种颜色最多出现一次。
不难想到一个 (Theta(nc)) 的dp做法，我们可以设 (f_{i,j}) 表示拿出 (i) 个巧克力之后桌上有 (j) 个巧克力的概率，可以得到:
但是这道题有多组数据，所以还是会被卡。
但是我们发现我们这个东西可以使用矩阵优化做到 (Theta(c^3log n)) ，可以勉强卡过去。
我们可以发现，其实就是要求有 (m) 种颜色出现奇数次， (c-m) 种颜色出现偶数次，可以发现答案就是:
（使用指数型指数函数是因为这是个序列，是有顺序的）
我们发现后面这个式子可以使用二项式定理展开，即:
于是我们就可以在 (Theta(c^2)) 的时间复杂度之内解决这个问题了。
( exttt{Code})
Shuffling
题目大意
有一个排列 (1,2,...,n) ，有另外两个排列 (a_{1,2,...,n},b_{1,2,...,n}) ，每次可以把当前排列的 (a_i) 位置移到位置 (i)，问当前排列变成 (b) 排列的最小步数。
(nle 520)
思路
不难看出其实这就是一个置换。
我们如果把移动抽象成一条边，那一次置换其实就是所有环旋转一次，那我们就可以知道我们每个环要移动多少次（在模环的大小的意义下），于是我们就可以使用拓展中国剩余定理解决了。
注意： 如果您的拓展中国剩余定理写得比较丑，您应该开一个 ( ext{int128}) 。
( exttt{Code})
奇怪的数学题
题目大意
定义 (sgcd(n,m)) 表示 (n,m) 的次大公因子，给定 (n,k) ，求出:
答案对 (2^{32}) 取模。
思路
让我又一次地体会到了 ( exttt{Min-25}) 筛的毒瘤。。。如果不会可以戳这里学习一波。。。
首先，不难想到 (sgcd(i,j)=dfrac{gcd(i,j)}{ ext{LPF}(gcd(i,j))})
其中 ( ext{LPF}(i)) 表示 (i) 的最小质因子。于是，答案就是:
（减 (1) 是因为 ((1,1)) 会算两次）
看到这个式子，我们发现后面那个东西显然可以使用杜教筛筛出来，然后直接整除分块即可。考虑前面那个东西，我们这个东西似乎可以 ( exttt{Min-25}) 筛筛出来，但是这并不是一个积性函数。但是如果我们假设我们要求积性函数 (f(x)=x^k,xin mathbb{P}) 的前缀和，我们观察我们 (g(n,i)) 的转移：
我们发现其实我们除以 ( ext{LPF}(d)) 其实就相当于去掉最小质因数的贡献，在式子就相当于去掉 (mathbb{P_i}^k) ，直接累加后面那一坨就好了，如果不理解可以见代码或者不管直接暴力理解 (g(n,i)) 的含义也可以，就相当于钦定 (mathbb{P_i}) 为最小质因数计算贡献。
我们发现还有问题需要解决：
-
如何计算质数处的取值
-
如何计算 (g(n,0))
首先第一个问题更好解决，我们发现质数处的取值为 (1)，即求出质数的个数，可以使用这道题的方法解决，大概意思就是说我们假定我们要求 (I) 的前缀和，那么最后 (g(n,|mathbb{P}|)) 就是答案。
考虑第二个问题，其实就是要求：
这个显然可以使用第二类斯特林数展开得到：
这个可以直接暴力斯特林展开，然后再用有限微积分求到。（应该非常好求吧？（伦敦雾
但是这道题是直接自然溢出，所以不好求逆元，于是我们就只好麻烦一个找到 (i+1) 的倍数除掉之后再乘上去，反正都是 (Theta(k^2)) 的。至于为什么我觉得非常显然，考虑剩余系即可。
于是，我们就解决了这道题了。时间复杂度 (Theta(dfrac{n^{frac{3}{4}}}{log n}++n^{frac{2}{3}}+k^2)) ，足以卡过去。
( exttt{Code})
Chinese remainder theorem again
题目大意
给出 (n,a) ，以及 (M_{1,2,..,n}) ，求出最小的 (x) 使得 (xequiv -apmod {M_i},s.t. 1le ile n) 。
(1le nle 10,1<M_i<100)
思路
很简单，不难发现答案就是 (operatorname{lcm}(M_1,M_2,...,M_n)-a)，据说直接拓展中国剩余定理会因为常数过大而T飞。。。( 不会吧？阿sir？
( exttt{Code})
很简单，懒得给了。
美妙的序列
题目大意
给出 (T) 组询问，每次给出一个 (n) ，问有多少个 (1 o n) 的排列满足从该排列 任意位置 切开，左边最大值大于右边最小值。
答案对 (998244353)取模，保证 (T,nle 10^5) 。
思路
我们通过打（OE）表（IS）发现如果我们设 (f_n) 表示长度为 (n) 时的答案，那么有递推式:
这里解释一下，就是说如果我们在一个排列放 (1 o k) 的任一排列，后面放剩下的 (n-k) 个，如果后面满足条件，那么该排列肯定不合法，因为从中间切开肯定就萎了。重点是为什么后面必须满足条件，这是因为这样保证不会算重，自己想一下就会明白为什么，自然语言不好解释。
这个式子显然可以用分治 ( ext{FFT}) 做到 (Theta(nlog^2n)) 。
然后我们移项之后发现：
然后我们就可以用多项式求逆做到 (Theta(nlog n)) 了。