首页 > 其他分享 >福州三中集训 2024.8.3

福州三中集训 2024.8.3

时间:2024-08-03 22:21:40浏览次数:15  
标签:frac 2024.8 sum times 三中 2n 集训

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

相关文章

  • 2024.8 做题记录
    8.1P6222\[ans=\sum_{T=1}^nT^kS(\frac{n}{k})\sum_{d\midT}d\mu^2(d)\mu(\frac{T}{d})\]令\(f(T)=\sum_{d\midT}d\mu^2(d)\mu(\frac{T}{d})\),f为积性函数,讨论\(f(p^k)\)的取值。P10636枚举第一个点和第三个点的横纵坐标之差\(i,j\),第二个点有\(gcd(i,j)-1\)种选择......
  • 24暑假集训day2上午
    上午内容:基础数据结构1.链表分类:单向和双向单向:当前链表只指向下一个元素双向:对于每个元素,记录其前面一个元素,也记录其后面一个元素。注意:链表不建议使用STL的某些元素进行替代,手写链表更为方便。1.单向链表做法:维护每个元素编号,然后维护nx指针,表示当前元素的下一个......
  • 24暑假集训day1上午
    上午内容:枚举递推贪心广告:推荐此题单1.枚举枚举:最基础、最容易想到本质:不重复,不遗漏T1数的划分问题简述:将整数\(n\)分成\(k\)份,且每份不能为空,任意两个方案不相同(不考虑顺序)。方法:搜索关键:有顺序具体步骤:尝试从大到小进行拆分,我们记录当前数剩下总和,记录当前还需......
  • 24暑假集训day3下午
    实现代码:intexgcd(inta,intb,int&x,int&y){ if(b==0){ x=1; y=0; returna; } intd=exgcd(b,a%b,x,y); intk=x; x=y; y=k-(a/b)*y; returnd;}intmain(){ inta=read(),b=read(); intx,y; intd=exgcd(a......
  • 24暑假集训day3上午
    进制转换一个\(m\)进制的数字\(\overline{a_0a_1\cdotsa_k}\)实际上是\(a_0m^k+a_1m^{k-1}+\cdots+a_k\)。\(10\)进制转\(m\)进制:每次除以\(m\)并取出余数。\(m\)进制转\(10\)进制:计算\(a_0m^k+a_1m^{k-}+\cdots+a_k\)。进制转换问题简述:将\(n\)进制数转换......
  • 24暑假集训day2下午
    下午内容:STL差分前缀和倍增1.STL#include<iostream>#include<queue>#include<cmath>#include<algorithm>#include<vector>#include<cstring>#include<cstdio>#include<set>#include<map>#include<uno......
  • 24暑假集训day6上午&下午
    DP概念状态、转移方程、初始化先放一张图(相信都能理解:状态、转移方程、初始化的含义,随便引入斐波那契数列的题)入门题Problem1斐波那契数列\[f_i=f_{i-1}+f_{i-2}\]组合数转移方程:\[C(n,m)=C(n-1,m-1)+C(n-1,m)\]\[C(n,0)=1\]杨辉三角:\[f[i][j]=f[i-1][j-1]+f[i-1]......
  • 24暑假集训day5下午
    DFS本质:一种用于遍历或搜索树或图的算法。所谓深度优先,就是说每次都尝试向更深的节点走。该算法讲解时常常与BFS并列,但两者除了都能遍历图的连通块以外,用途完全不同,很少有能混用两种算法的情况。关键:递归调用自身对其访问过的点打上访问标记,在遍历图时跳过已打过标记的点,以......
  • 24暑假集训day5上午
    图论差分约束有\(......
  • 24暑假集训day4上午&下午
    基础图论图的存储方式无向边可以拆成两条有向边1.邻接矩阵邻接矩阵:若\(......