旋转序列来源：IzbornePripreme2022(CroatianIOI/CEOITeamSelection)Day1,ProblemBhttps://qoj.ac/contest/956/problem/4326两个串之间\(1\)匹配的次数总和为\(k\timesl\)，并且共有\(n\)次匹配。于是答案的上界为\(k\timesl\)个球放进\(n\)个盒子，最小化

记号1设\(f(x)\)是关于变元\(x\)的多项式,则对正整数\(n\),记\(\left[x^n\right]f:=f(x)\)的\(x^n\)项系数.例如,若$f(x)=-3+5x+7x^3$,则$\left[x^0\right]f=-3,\left[x^1\right]f=5,\left[x^2\right]f=0$,$\left[x^3\right]f=7$.一般地,由微积分中

思路容易看出来是个DP题，但是你发现DP的起点是不好确定的，于是假定第一条边的起点是黑色。然后你发现设为白色的贡献与黑色是相同的，于是直接令第一条边的起点是黑色，最后答案乘以\(2\)即可。然后就可以愉快的DP了。首先枚举每条边白色点的数量\(k\)，定义\(dp_{i,0/1}\)

思路定义\(vis_i\)表示数\(i\)在序列中出现的次数。如果我们选出\(k\)个数，答案就是（其中\(m\)表示\(\max(c_i)\)）：\[\sum_{i=1}^m\frac{\binom{n}{x}-\binom{n-vis_i}{k}}{\binom{n}{x}}\]显然，我们只枚举序列中存在的元素，时间复杂度\(\Theta(n^2)\)，过不

杂题乱刷目录杂题乱刷P7231COCI2015-2016#3]DOMINOCF888GXor-MSTCF1886E题目大意solutionCF1209G2IntoBlocks(hardversion)题目大意solutionCSP-S2019Emiya家今天的饭题目大意preface正解WhatIhavegotP4151[WC2011]最大XOR和路径[CF510D]FoxAndJumping题目大意so

目录CF1956FNeneandthePassingGame题目大意solutionCF1942EFarmGame题目大意solutionCF1942GBessieandCards题目大意solutiontipsCF1943D2题目大意solutionE3.Trails题目大意solutionCF1956FNeneandthePassingGame题目大意给定\(n\)个点，每个点有两个系数\([

TheMethodofSnakeOil进行组合求和的蛇油法。确定求和所依赖的自由变量，例如\(n\)。为您正在处理的求和命名；称之为\(f_n\)。让\(F(x)\)成为\(f(n)\)的生成函数，即您想要求和的和。将和乘以\(x^n\)，然后对\(n\)求和。您的生成函数现在表示为对\(n\)的双重求和，以及

2024.6.16挑了套简单ABC找找状态，做了E、F、G。E稍微思考一下会发现有用的量是每种字母选的个数，记第$i$种字母用了$a_i$个，那么答案就是$\binom{n}{a_1}\binom{n-a_1}{a_2}\binom{n-a_1-a_2}{a_3}...\binom{n-a_1-a_2-...-a_{n-1}}{a_n}$。化简一下就是

CF1204E=998244853.Natasha,SashaandthePrefixSumsNaCly_Fish最喜欢的数字是\(n\)和\(1\)；\(\mathsfE\color{red}\mathsf{ntropyIncreaser}\)最喜欢\(m\)和\(-1\)。有一天，她们在一起写出了一个长度为\(n+m\)，有\(n\)个\(1\)和\(m\)个\(-1\)的序列\(

AzusidNya17分钟前：多项式快速幂\(n\logn\)跑\(1e5\)跑了\(4\)秒，乐删除P5488差分与前缀和给定一个长为\(n\)的序列\(a\)，求出其\(k\)阶差分或前缀和。结果的每一项都需要对\(1004535809\)取模。\(1\len\le10^5\)\(0\lea_i\le10^9\)\(1\lek\l

记录一下，下文的除法非特殊注明都是向下取整。求\(F(n,k)=\sum_{i=0}^{k}\binom{n}{i}\pmodp\)。首先使用卢卡斯定理。\[\begin{aligned}&\sum_{i=0}^{k}\binom{n}{i}\\=&\sum_{i=0}^{k}\binom{\frac{n}{p}}{\frac{i}{p}}\binom{n\bmodp}{i\bmodp}\\=&\s

SCP-CN-3999，跨越天堂。P10144如果一个区间\([L,R]\)满足条件，则\(\max(a_i,h-a_i)\)在\([L,R]\)上单谷。观察到能让\(\max(a_i,h-a_i)\)和\(\max(a_{i+1},h-a_{i+1})\)变号的\(h\)分割点只有\(\mathcal{O}(n)\)个，于是可以用一种类似于扫描线的方法记录每一个符

二项式反演简介二项式反演可以用来解决一些计数问题，是连接至少/至多与恰好两类函数的桥梁。形式一\[f(n)=\sum_{i=0}^n(-1)^i\binom{n}{i}g(i)\\g(n)=\sum_{i=0}^n(-1)^i\binom{n}{i}f(i)\]证明代\(g(n)\)入第一条式子。\[\begin{aligned}f(n)&=\sum

默认\(n\)为常数，\(x\)为自变量。幂（前提条件为\(n\ne1\)，\(n=1\)时平凡）\[n^x=\Delta\left(\dfrac{n^x}{n-1}\right)\]\[\Delta\left(n^x\right)=(n-1)n^x\]下降幂（前提条件为\(n\ne-1\)，\(n=-1\)时见调和数部分）\[x^{\underlinen}=\Delta

题意：在\([1,n]\)的区间里放\(m\)棵树，每棵树的高度为\(k\)。求有多少种放置树的方法，满足：每个树都在整点上，且每个点最多只能放一棵树。存在一种砍倒树的方案，使得树倒了之后不会越界，也不会有某个点被超过一棵树占据。你可以自由选择树向左倒（也就是占据区间\([x-k,x]\)）

对于所有长为\(n\)值域在\([1,m]\)的正整数序列，对于每一个\(1\leqslanti\leqslantm\)记\(c_{i}\)表示\(i\)在\(a\)中的出现次数，定义其权值为\(\prod_{i=1}^{m}c_{i}^{c_{i}+k}\)，求所有序列的权值和对一个大质数\(p\)取模的结果(特别的,我们定义\(0^0=1\)，且对于

\(\text{ByDaiRuiChen007}\)1.[ARC080F]PrimeFlipProblemLink数轴上有\(n\)个点\(a_1\sima_n\)的颜色是黑色的，其余颜色为白色。每次操作可以选连续\(p\)个位置反色，其中\(p\)必须是奇素数。求全部位置染白的最小操作次数。数据范围：\(n\le100,a_i\le10^7\)

这一章主要讲解各种组合恒等式。但是事实上，有很大一部分都能用有限微积分、OGF、EGF之类的武器轻松搞定。组合恒等式组合数定义朴素定义：\[\binomnm=\dfrac{n!}{m!(n-m)!}\]下降幂定义：\[\binomnm=\dfrac{n^{\underlinem}}{m!}\]组合数递推式（Pascal'sIdenti

令\(c_i\)为第\(i\)位带来的进位的值，令\(c_{-1}=0\)。考虑如果知道了\(c_{i-1},c_i\)的值，\(a_i,b_i\)有多少种选法：\(c_{i-1}=0,c_i=0\)，\((a_i,b_i)=(0,0),(0,1),(1,0)\)。\(c_{i-1}=1,c_i=1\)，\((a_i,b_i)=(1,1),(0,1),(1,0)\)。

writeby小超手123题意：现在有四种物品，分别有\(n_{1},n_{2},n_{3},n_{4}\)个，有多少种排列物品的方案使得任意两个相邻物品的种类不同。\(n_{1},n_{2}\le200,\\n_{3},n_{4}\le50000\)。分析：可以考虑先把物品\(A,B\)排列好，再把物品\(C,D\)插入进去。需要注意的

Description给出\(n,k\)，求一个长度为\(n\)的数组\(a\),满足有恰好\(k\)对数对\((i,j)(1\leqi<j\leqn)\)满足\(a_i+a_j\)为完全平方数。如果不存在，输出\(-1\)。linkSolution显然如果\(k>\binom{n}{2}\)就一定无解。构造时会发现肯定要尽量弄成相同的

注：其实前面还有一些内容，如矩阵树定理一类的东西。但是由于我还没有整理好所以把整理好的部分弄上来。一些DFT/IDFT的算法学多项式是一个很有意思的过程。开始的时候你会学习FFT/NTT知道怎么样通过DFT/IDFT快速计算多项式的各种操作。然后你会深入学习多项式的各种运

今天讲了不少有趣题，但是可惜很多题没有提交入口，不牛。先放个课件吧。度盘Codechef-CyclesAndColorings加强给出一张\(n\)个点\(m\)条边的无向连通简单图，你需要完成以下两个任务的其中一个，输出方案。给出一个三染色方案。找一个奇环，使得删去它后图仍连通。（注意：这里

前言本文章将会持续更新，主要是一些个人觉得比较妙的题，主观性比较强（给自己记录用的），有讲错请补充。带！号的题是基础例题，带*号的是推荐首先完成的题（有一定启发性的）。组合数P6620[省选联考2020A卷]组合数问题运用斯特林数好的例题，普通幂转下降幂。用到第二类斯特林数。\[

BinomialSum如果我们有一个微分有限函数\(F(z)\)，还有另外一个生成函数\(G(z)\)，一个数列\(a\)，如果我们能对\(k\in[0,n]\)的每一个\(k\)快速求出\(G^k(z)\)的前\(n\)项系数带权和，即\[b_k=\sum_{i=0}^na_i[z^i]G^k(z)\]那么我们可以在\(\Theta(n)\)的时间复杂度内