福州三中集训 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