Jason Fan.

fdbc2997623a61cf73a7235ddd759531cfe552c1246c0f6db78325b1498830416153d2fce5322038cdb587dc0afec73701d448c37bd12dcac6d0d20b12262e0f758884fe6fbfd23cbc5f4fd990188844b10c8bb6ac34a3ce56a2b73c064d2c78b8fd69e41ea14e4ce888ac2ee1352bfb63a0d4d1b43c0a8b2a8e7532efda5a4112d79241d8830e5bd40895eaee93e46076a4813577702aefb874cc87d61dfb619967792e86c0c9b1a5c27dcb1f36d2f8826ddb209befc632e4b079b118dd2ab8601dcb1fd9e4c6411ebb567e30c78df11dad9f1057b80ccec5628a069691e5f7b771decfe392554ba7830b6eacd1547cf46decce2e457c7d4 ...

[NOIP2020] 微信步数 暴力 先定义走完一次 1∼n1\sim n1∼n 的步骤为一轮。 考虑所有点一起按照步骤走下去，每步可能会使原本存在的点出界。我们维护每步后剩余的点，累加即可。具体地，每个维度互不干扰，且对与一个维度而言，删除的必然是从左一段连续的区间和从右一段连续的区间，若在该步下维度 iii 剩下 [li,ri][l_i,r_i][li​,ri​] ，那么剩余的总点数为 ∏i=1k(ri−li+1)\displaystyle\prod_{i=1}^{k} (r_i-l_i+1)i=1∏k​(ri​−li​+1) 。 我们只要一步一步模拟即可，直到没有点剩余。另外判断无穷步：在第一轮后回到起点且还有点剩余。 复杂度为 O(Tnk)O(Tnk)O(Tnk) ，其中 TTT 为最多跑了几轮。 CODE 1234567891011121314151617181920212223242526272829303132333435363738394041typedef long long ll;const int N = 500010;const int M = 16;const ...

给你 n+1n+1n+1 个点，求穿过它们的 nnn 次多项式。于是你想到了待定系数高斯消元，不过这 O(n3)O(n^3)O(n3) 的太烂了。于是我们引入拉格朗日插值法，通过构造法整出多项式。 拉格朗日插值法 记这 n+1n+1n+1 个点为 (x0,y0),(x1,y1),(x2,y2),…,(xn,yn)(x_0,y_0),(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n) (x0​,y0​),(x1​,y1​),(x2​,y2​),…,(xn​,yn​) 定义拉格朗日基本多项式 ℓi(x)\ell_i(x)ℓi​(x) ℓj(x)=∏i≠jx−xixj−xi\ell_j(x)=\prod_{i\ne j}\frac{x-x_i}{x_j-x_i} ℓj​(x)=i=j∏​xj​−xi​x−xi​​ 很容易发现一个性质： ∀i≠j:ℓj(xi)=0\forall i\ne j :\ell_j(x_i)=0 ∀i=j:ℓj​(xi​)=0 ℓj(xj)=1\ell_j(x_j) =1 ℓj​(xj​)=1 于是我们得到拉格朗日插值多项式为： L(x)=∑j ...

计算几何？ 题意简述 给你 nnn 个点 pi=(xi,yi)p_i=(x_i,y_i)pi​=(xi​,yi​) ，问你有多少条过原点的直线满足：所有点在该直线上的投影呈轴对称。若有无穷个直线输出 −1-1−1 。 题解 考虑我们有一条直线 y=kxy=kxy=kx ，为了避免误差我们用向量表示 (a,b),k=ba(a,b),k=\dfrac{b}{a}(a,b),k=ab​ 。 考虑 nnn 个点在该直线上的投影，可以用 点积，考虑其几何意义：从原点到某点 pip_ipi​ 的向量在直线上的投影 乘上 向量 (a,b)(a,b)(a,b) 的长度。这可以表示每个点在直线上投影的相对位置。 我们已经把二维转化成一维了，接着要满足 nnn 个数在数轴上对称。若对称必然存在一个中心点为所有点的平均值，即 o=1n∑i=1naxi+byio = \frac{1}{n}\sum_{i=1}^n ax_i+by_io=n1​∑i=1n​axi​+byi​ ，易得其在二维平面上的点为 O(∑i=1nxin,∑i=1nyin)O\left(\dfrac{\sum_{i=1}^n x_i}{n} ...

初赛知识点，时间复杂度分析

CQOI2011 - 放棋子 题意 给你一个 n×mn\times mn×m 的棋盘，和 ccc 种颜色的棋子，每种棋子有 aia_iai​ 个。要求将所有棋子放到棋盘上，满足不同颜色棋子不能同行或同列。输出方案数，对 109+910^9+9109+9 取模。 1≤n,m≤30,1≤c≤10,∑ai≤max⁡(250,n×m)1\le n,m\le 30,1\le c\le 10, \sum a_i \le \max(250, n\times m) 1≤n,m≤30,1≤c≤10,∑ai​≤max(250,n×m) 题解 设计 DP 状态 f(i,j,k)f(i,j,k)f(i,j,k) 表示用了 1∼k1\sim k1∼k 种颜色的所有棋子，选了 iii 行 jjj 列填充的方案数。因为不同颜色棋子不能同行或同列，考虑枚举新颜色的棋子占了几行几列，这对原来棋子是无影响。 f(i,j,k)=∑l=0i−1∑r=0j−1(n−li−l)(m−rj−r)f(l,r,k−1)g(i−l,j−r,ak)f(i,j,k)=\sum_{l=0}^{i-1}\sum_{r=0}^{j-1}\bino ...

HEOI2013 SAO 题意 给出一颗边有方向的树，求该图的拓扑序数量。 n≤1000,mod=109+7n\le 1000,mod= 10^9+7n≤1000,mod=109+7 题解 f(u,i)f(u,i)f(u,i) 表示以 uuu 为根的子树，uuu 子树内排名为 iii 的方案数。 考虑转移，枚举 v∈son(u)v\in son(u)v∈son(u) ，将 f(v,j)f(v,j)f(v,j) 合并到 f(u,i)f(u,i)f(u,i)，（两列数，各自顺序不打乱的合并） vvv 在 uuu 前 再枚举 vvv 子树中有 k(k≥j)k(k\ge j)k(k≥j) 个排在 uuu 前面，对 f(u,i+j)f(u,i+j)f(u,i+j) 累加。 f(u,i+k)′←f(u,i+k)+(i+k−1i−1)(sizu+sizv−i−ksizv−k)f(u,i)f(v,j)f(u,i+k)' \gets f(u,i+k)+\binom{i+k-1}{i-1}\binom{siz_u+siz_v-i-k}{siz_v-k}f(u,i)f(v,j) f(u,i+k ...

笛卡尔树，树形dp。 SP3734 PERIODNI 题意 给定一个 NNN 列的表格，每列的高度各不相同，但底部对齐，然后向表格中填入 KKK 个相同的数，填写时要求不能有两个数在同一列，或同一行，下图中 b 是错误的填写， a 是正确的填写，因为两个 a 虽然在同一行，但它们中间的表格断开。 1≤N,K≤500, hi≤1061\le N,K \le 500,\,h_i\le 10^6 1≤N,K≤500,hi​≤106 题解 先考虑一个 n×mn\times mn×m 的矩形，选 kkk 个格子，不能出现同行同列的方案数。 (nk)×(mk)×k!\binom{n}{k}\times \binom{m}{k} \times k! (kn​)×(km​)×k! 考虑原题，因为连续的一行内只能放一个，所以可从下到上做如下切割（当前区间 [l,r][l,r][l,r] 选择区间最小的 hxh_xhx​，一刀切，得到左右两个独立的块 [l,x−1][l,x-1][l,x−1] 和 [x+1,r][x+1,r][x+1,r]。重复即可）。这个操作实际上对区间建笛卡尔树，树上每个节点对应一 ...

fdbc2997623a61cf73a7235ddd7595317a2ccbb3a6c7b9c72acd69409a28908a2eab4a875d4faa8796f7077afb872d6cbdd6e21f4ea22b600620754df3763a2cb51cbab58fde68b8787157f69276dfa0530736b3e52bc5bae4e6e6fc220f485fec19e8183fe155b2d8dc05d91b2ee69fd9d5c9fd74c3dd1567bbb8fd897dffd221e539396ce04b21e3e3264ae651460af002b0252f275048c22d429b49c30e6097b95b8e3e22ff11a9bf9cb71f25d829fa64cbf2db92c29981a62e316c84a594ab53c14599ae9f13cae6f42015b07c189911bbaad12c1bf0e4d87439cb282a136bcc20818cf42eb1bcf28160e23db3dc323094d4cda9a2fbd ...

XJ - NOI2021赛前训练题20 「2020~2021 年信息学多校联合训练 NOI2021 模拟赛」