福州三中集训 2024.8.3
——找规律、构造专题
早上讲了好多构造……脑袋快炸了，下午再搞比赛，脑子感觉就是火山……
早上老师先来了道数学题开开胃，求：
\[\sum_{i=1}^n\times i\times i! \mod n \]我：这。。慢慢拆吧，头脑不需要风暴。呐——
\[\sum_{i=1}^n\times i\times i! \\ =(i+1)\times i!-i! \\ =(i+1)!-i! \\ =[\ (\ i+1\ )!-i!\ ]\ +[\ i!-(i-1)!]\ +\cdots +[(2!-1!)] \\ =(i+1)!-1 \\ =(n+1)!-1 \\ \\ \because \ n\mid(n+1)!-1 \\ \therefore (n+1)!-1\mod n =n-1 \]刚肝完一道数论，又来了道卡特兰数，大概公式：
\[f(n)=\begin{cases} 1\ \ \ n=[0,1] \\ \sum_{i=1}^{n}\ f(i-1)\times f(n-1)\ \ n \ge 2 \end{cases} \]老师上这玩意的时候，直接调出了 oiwiki
大概思路是，在 \(2n\) 中随便选 \(n\) 个数，所以方案数为 \(C_{2n}^{n}\)，再减去 \(C_{2n}^{n-1}\) （不合法）
推理过程嘛——脑袋不够用！
\[C_{2n}^n-C_{2n}^{n-1}\\ =\frac{(2n)!}{(n!)^2}-\frac{(2n)!}{(n-1)!\times (n+1)!}\\ =\frac{(2n)!\times (n+1)-(2n)!\times n}{n!(n+1)!}\\ =\frac{(2n)!}{n!(n+1)!}\\ =\frac{C_{2n}^n}{n+1} \]我：这不是普及的难度吗。。。
后面又搞了些构造的难题，很狗啊！！
又给了我们一些数，求最多有几个数字异或值为素数。
老师：打表 列表观察规律，然后!@#$%&……(*&^%)。
对，后面压根没听，直接和同学自己研究出了另一种方法：
对于任意两个 \(a_i,a_j\)，若 \(a_i \oplus a_j\) 为素数，则在俩数连上一条边，最后将入度最大的度数 \(+1\) 即可得到。
（老师一边讲课，一边捋自己的山羊胡，一边在倒水和喝水间徘徊）
标签：frac,2024.8,sum,times,三中,2n,集训 From： https://www.cnblogs.com/Atserckcn/p/18341179