CF1149EElectionPromises这个题目最难下手的地方在于：可以对相邻的城市进行任意修改，这导致难以确定后继状态。但是还是可以使用\(\operatorname{SG}\)函数！下面设\(f_u=\operatorname{mex}\{f_v\}\)，这个可以直接拓扑排序求。考虑这样一个状态：除点\(u\)外所有点的当前\(h\)均为\(0\)，此时\(\operatorname{SG}(x)=\omega_{f_u}\cdoth_u\)，其中\(\omega_k\)表示\(k\)阶无穷大。先手必败当且仅当\[S_k(x)=\bigoplus_{f_u=k}{h_u}=0,\fo
ARC076F-Exhausted?[题目大意]\(有m个座位，分别位于坐标为1,2,3,...,m的地方；n个客人，第i位客人只坐位于[0,li]∪[ri,m]的座位。每个座位只能坐一个人，问最少需要添加几个座位才能使所有人坐下？\)[Solution]本题考察对霍尔定理的理解，$对于二分图G=,设|V_1|而霍尔定理有一个推论，就是若使G中存在完美匹配，则最少补充\(max\{0,|S|-|N(S)|\}\)条边回到本题，对于一个人，把他看做左部点，把座位1到m看做右部，将客人向所有\(i\in[1,l_i]\cup[r_i,m]\)连边因为左部S所对应的右部节点的形式为\([1,l]\c
CF1149EElectionPromises这个题目最难下手的地方在于：可以对相邻的城市进行任意修改，这导致难以确定后继状态。但是还是可以使用\(\operatorname{SG}\)函数！下面设\(f_u=\operatorname{mex}\{f_v\}\)，这个可以直接拓扑排序求。考虑这样一个状态：除点\(u\)外所有点的当前\(h\)均为\(0\)，此时\(\operatorname{SG}(x)=\omega_{f_u}\cdoth_u\)，其中\(\omega_k\)表示\(k\)阶无穷大。先手必败当且仅当\[S_k(x)=\bigoplus_{f_u=k}{h_u}=0,\fo
目录ImportanceSampling（IS）LightBVH[2018~2019]预构建BVH重建BVH基于BVHnode的ISReal-timeStochasticLightcuts[2020]莫顿序排序（MortonOrderSofting）构建LightTree基于Lightcuts的ISCutSharingReSTIR（ReservoirSpatio-TemporalImportanceResampling）[2020]ResampledImportanceSampling(RIS)WeightedReservoirSampling(WRS)基于屏幕空间的多光源RIS预处理光源pi
Hensel引理、原根一、Hensel引理Hensel引理：\(\mathsf{f(x)}\)是一个整系数多项式\(\mathsf{(\f(x)\inZ(x)\)}\)，对于素数p，整数a使得\(\mathsf{p^{k}\midf(a)}\)，\(\mathsf{(\f^{'}(a)，p\)=1}\)，即\(\mathsf{f(a)\equiv0\mod\p^{k}，f^{'}(a)\neq0\mod\p}\)。则在模p意义下恰有一个整数t使得\(\mathsf{f(a+tp^{k})\equiv0\(mod\p^{k+1})}\)。也就是在模\(\mathsf{p^{k+1}}\)的意义下
前言在计算机运行过程中，由于种种原因致使数据在存储过程中可能出现差错。为了能及时发现错误并及时纠正错误，通常使用一些编码方式。奇偶校验奇偶校验是一种添加一个奇偶位用来指示之前的数据中包含有奇数还是偶数个1的检验方式。对于一个二进制数：\(b_nb_{n-1}...b_2b_1\)，添加一个校验位s，采取偶校验，即校验位使新数据中的1的个数为偶数。新数据：\(b_nb_{n-1}...b_2b_1s\)。即\(b_n\oplusb_{n-1}\oplus...\oplusb_2\oplusb_1\opluss=0\)，则\(s=b_n\oplusb_{n-1}\oplus...\oplusb_2
同余、中国剩余定理一、同余(Congruence)1.令\(\mathsf{a,\b,\m}\)为整数，且$\mathsf{m\neq0}$。当满足\(\mathsf{m\mid(a-b)}\)时，称a与b模m同余，写作\(\mathsf{a\equivb\mod\m}\)例子：\(\mathsf{3\equiv27\mod\12}\)，\(\mathsf{-3\equiv11\mod\7}\)2.基本性质：同余兼容常用加法与乘法运算。如果\(\mathsf{a\equivb\(mod\m)}\)并且\(\mathsf{c\equivd\(mod\m)}\)，那么\(\mathsf{a+c\e
几何光学基本定律折射定律：\({\displaystylen_1\sini=n_2\sin\gamma}\)反射定律可当作折射定律在\(n_1=-n_2\)下的特例，得\(i=-γ\)，负号表示反射线和入射线分居法线两侧.\({\displaystyle当入射角(临界角)i=i_C=\arcsin(\frac{n_2}{n_1})}\)折射角=\(90°\)，折射线掠过介质表面，全反射。\(某透明介质对空气的全反射临界角为45°(折射角=90°),\)\(那么光从空气射向此介质时的布鲁斯特角等于\arctan(\sqrt{2})\)\(解释：{\displaystyle\sin45°=\fra
本题为3月23日23上半学期集训每日一题中B题的题解题面(写题解的时候学校oj已不可查看此题,下面的题面来自洛谷第1157题)题目描述排列与组合是常用的数学方法，其中组合就是从\(n\)个元素中抽出\(r\)个元素（不分顺序且\(r\len\)），我们可以简单地将\(n\)个元素理解为自然数\(1,2,\dots,n\)，从中任取\(r\)个数。现要求你输出所有组合。例如\(n=5,r=3\)，所有组合为：\(123,124,125,134,135,145,234,235,245,345\)。输入一行两个自然数\(n,r(1。输出所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每
前言最小割树（Gomory-HuTree）通过分治的思想，将图中的最小割关系建成一棵带权了树上问题。它的主要用途是求解全源最小割/最大流。前置知识：一种快速的最大流算法（Dinic/ISAP均可，FF/EK不行，HLPP虽然快但不方便求最小割树），本文中采用Dinic。最小割最大流定理：最小割=最大流分治思想下文中若无例外，均用\(O(\text{maxflow}(n,m))\)表示求一个\(n\)个点\(m\)条边的图上任意两点之间的最大流/最小割的时间复杂度。建立首先我们将全图看成一个集合。然后我们任选两个点\(s,t\)跑一遍最大流。然后你会发现，我们可以通过源点是否与其连通分成两个集合
