题目描述对于一个排列\(a\)，定义其权值如下：生成一个\((n+2)\times(n+2)\)的网格图，行列标号为\(0∼n+1\)，每次可以从\((i,j)\)走到\((i,j+1)\)或\((i+1,j)\)，且不能走到\((i,a_i)\)，权值为从\((0,0)\)走到\((n+1,n+1)\)的方案数。现在排列\(

个人认为思维难点相同的三倍经验：P3226[HNOI2012]集合选数、TFSETS-Triple-FreeSets。区别在于状压DP的方法。我们称不包含质因子\(2\)和\(3\)的数为\(2,3\texttt{-Free}\)的。对于\([1,n]\)内每个\(2,3\texttt{-Free}\)的整数\(u\)，可以列出以下的矩阵：\[\begi

本题解提供英文版，位于示例代码之后。Englishversionofthiseditorialisprovidedafterthesamplecode.官方题解竟然用Python来算高精度lcm，我来提供一个可以避免一切大整数运算的方法。考察\(u\getsP_u\)这张图的每个置换环。为了使答案字典序最小，显然需要从前往后

#include<bits/stdc++.h>usingnamespacestd;template<longlongmod=INT_MAX,typenameT0=longlong>classmodint{ private: T0x; longlongpositive(longlongx){ x+=(llabs(x/mod)+1ll)*mod; returnx%mod; } modint<mod>positi

从阶乘幂到斯特林数-caijianhong-博客园(cnblogs.com)题目描述Crash小朋友最近迷上了一款游戏——文明5(CivilizationV)。在这个游戏中，玩家可以建立和发展自己的国家，通过外交和别的国家交流，或是通过战争征服别的国家。现在Crash已经拥有了一个\(n\)个城市的国家，这

本题解提供英文版，位于示例代码之后。Englishversionofthiseditorialisprovidedafterthesamplecode.设行向量：\[A^{(k)}=\begin{bmatrix}a_1^{(k)}&a_2^{(k)}&\cdots&a_n^{(k)}\end{bmatrix}\]表示\(k\)次操作后每个节点点权的期望。特别地，\(A^{(0)}\)表

直接摘抄OI-wiki了。第二类斯特林数第二类斯特林数（斯特林子集数）\(\begin{Bmatrix}n\\k\end{Bmatrix}\)，也可记做\(S(n,k)\)，表示将\(n\)个两两不同的元素，划分为\(k\)个互不区分的非空子集的方案数。递推式\[\begin{Bmatrix}n\\k\end{Bmatrix}=\begin{Bmatrix}n-1\\k-1

NTT前置知识：FFTNTT，中文“快速数论变换”，是FFT在数论领域上的实现，比FFT更快，应用更广。对于FFT，因为其涉及到复数操作，对于某些需要取模的题不再适用。并且因为需要求正弦与余弦，使用时难以避免精度误差。这时就需要用到NTT来解决问题了。我们知道FFT的实现是在复平面上找

今、在zhengruioi.com上参加模拟赛时被卡常了。这道题目涉及对\(998244353\)取模的操作，故我使用我自制的由atcoder::static_modint改写而来的modint完成了代码，这两个板子大致如下：//modinttemplate<unsignedumod>structmodint{/*{{{*/staticconstexprintmod

CodeforcesRound957(Div.3)A-G题解A.OnlyPluses枚举思路：枚举\(a\),\(b\),\(c\)增加的次数，维护最值即可。代码：#include<bits/stdc++.h>usingnamespacestd;#definefffirst#definesssecond#definepbpush_back#defineall(u)u.begin(),u.end()#

本文为第二届你要魔怔杯鲜花大赛！！！投稿作品。前言这是一个\(\bmod\11\)的世界。假设这个世界与地球类似（不妨称它为E球），但是所有的数都是\(\bmod\11\)意义下的。在正文和注解部分书写一个十进制数时我会用0d作为前缀。下文用\(A\)代替\(10\)。人名都是随机找的。

我让cz搬这道题，cz给搬了，于是来写个题解（考虑一个朴素的贪心：每次选择一个到根路径价值和最大的叶子，将价值和累加进答案，并把这条链价值清零。这个贪心的正确性显然（可以交换法证明），很容易用数据结构维护做到\(O(n\logn)\)。但是这样太不优美了，而且数据结构比较难写，于是考虑一个

区间最值操作基础题，但是有点码农。依然考虑势能线段树，维护区间和\(\textrm{sum}\)、最大值\(\textrm{M1}\)、次大值\(\textrm{M2}\)、最大值个数\(\textrm{Mcnt}\)、最小值\(\textrm{m1}\)、次小值\(\textrm{m2}\)、最小值个数\(\textrm{mcnt}\)，另外需要区间加标记\(\tex

场切了1E，第一次上IGM，纪念一下。多图警告。我们称题目中的一个方块为“某色混凝土”。感受一下，发现本题主要的难点在于这些混凝土方块排布得太紧密了，导致容易出现互相遮挡的现象，进而难以构造。于是，我们先思考能否通过一些操作使得这些混凝土互相分离。如下图的方式可以将每两

前置知识https://www.cnblogs.com/caijianhong/p/template-crt.htmlhttps://www.cnblogs.com/caijianhong/p/template-fft.html题目描述任意模数多项式乘法solution首先我们打开https://blog.miskcoo.com/2014/07/fft-prime-table这篇文章找到\(998244353\)附近的几个质

萌萌F题，上大分。首先，如下定义\(g(i)\)：\(g(1)=\lfloor\sqrt{a_1}\rfloor\)；对于所有\(i>1\)，\(g(i)=\lfloor\sqrt{g(i-1)+a_i}\rfloor\)。也就是将\(f(i)\)的每一步运算后都向下取整。注意到\(\lfloorf(i)\rfloor=g(i)\)恒成立，于是我们只需要转而求每次修改后\(g(n

先不考虑构造字典序最小的方案，只考虑求出最小的\(\sum\limits_{i=1}^{N-1}|A_{i+1}-A_i|\)。设定义域为\([L_i,R_i]\)的函数\(F_i(x)\)表示考虑后缀\([i,N]\)，令\(A_i=x\)时上式最小的值。初值为\(F_N(x)=0,(x\in[L_N,R_N])\)。显然有转移方程：\[F_i(x)=\min\limits_{y

非常精彩的转化！显然，树是二分图。由König定理，我们知道：二分图最小点覆盖等于最大匹配。因此枚举点覆盖\(S\)，则一条边\((u,v)\)可以被选择，当且仅当\(u\inS\lorv\inS\)，在所有可以选择的边上跑最小生成树即可。我采用的是Kruskal算法，时间复杂度为\(O(2^nn^2\logn)\)，可

初三多项式的运算练习题解美好的下午时光要拿来写题解呜呜呜，一篇一篇地鸽得了。有些题要用到GF的知识，或许我可以找时间讲一下？贴一份我的FFT和NTT的板子。FFT：#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;intn,m,limit,f[1<<22],g[1

对于每个询问，可以把这\(r-l+1\)个袋子包合并成一个有\(\sum\limits_{i=l}^ra_i\)个金币和\(\sum\limits_{i=l}^rb_i\)个银币的袋子。\([l,r]\)外的袋子同理也可以这样合并。假设\(sum_a=\sum\limits_{i=1}^na_i,sum_b=\sum\limits_{i=1}^nb_i\)，\(

A.多项式推柿子：\[\begin{aligned}&\sum\limits_{k=0}^{n}b_{k}(x-t)^{k}\\=&\sum\limits_{k=0}^{n}b_{k}\sum\limits_{i=0}^{k}\binom{k}{i}x^{i}(-t)^{k-i}\\=&\sum\limits_{0\leqslanti\leqslantk\leqslantn}\binom{k}{i}b_{

好像比题解劣一个\(n\)，但是也跑的很快。首先说明，问题等价于计算有多少种本质不同的方案使得整个序列被删完，证明省略。考虑用区间的方式表述这些操作，具体的，忽略删除后的移位操作，将每次删除的左右段点视为一个区间，则一定会有：区间的并是\([1,n]\)。区间之间要么不交，要么包含。

总算铂金组场切一题。似乎做麻烦了，而且常数蛮大的，但是没啥思维难度，记录一下。对于每一个需求，我们将其放置在平面直角坐标系的\((m_i,b_i)\)位置。另外，自然有一个\((0,0)\)需求，也同样处理这个点。我们需要支持插入一个点的操作，并维护出答案。先考虑不需要动态插点，只在最后求

Namid[A]me好听呢。可惜了。今天DP专题感觉laofu选的题有点经典，导致我有一半时间在摸鱼，不过还是写了点题的。怎么西工大附中有糖醋茄子这种神秘菜啊。ICPC2020MacauBBoringProblem其实不一定懂完了，试着说一说。显然询问没什么用，问题本质是要求解一个AC自动机上游

SlopeTrick总结注意：SlopeTrick并不是斜率优化，斜率优化的英文是ConvexHullTrick。算法适用性SlopeTrick通常用于维护具有如下性质的函数：连续。是分段一次函数。是凸函数。每一段的斜率较小（通常为\(O(n)\)），且均为整数。常常用于优化动态规划。不失一般性，约定本