传送门发现\(nk\)可行，猜测是\(O(nk)\)的DP。容易想到设计\(dp[i][j]\)表示前\(i\)个物品，允许恶魔使用\(j\)次魔法的最大价值。但是这样转移是有后效性的，因为恶魔可能在只考虑前\(i\)个物品的时候与只考虑前\(j\)个物品的时候对于某个物品是否要使用魔法的决

传送门夏天近了，又到了恋爱的季节，小Q家门前的苹果树上结满了红红圆圆的苹果。这株苹果树是一个有着\(n\)个结点的有根树，其中结点被依次编号为\(1\)至\(n\)。\(1\)号结点为根，其余每一个结点的父结点一定是某个编号较小的结点。每一个结点上都有一些苹果，第\(i\)个结点上有\(a_i(a_

B求长度\(\gek\)的区间去掉前\(k\)大剩下权值和的最大值。\(n\le1e5,k\le100\)。一个比较暴力的办法就是维护出每个区间的答案，考虑一个位置什么时候被扣掉。首先计算出左边前\(k\)个与右边前\(k\)个比\(a_i\)大的位置，然后考虑匹配，形成的区间里都减去\(a_i\)。然

题意给定\(n\)种颜色的球，每一种有\(k\)个，随意排列\(n\timesk\)个球，然后将每种球的左边第一个球变为第\(n+1\)种颜色，问操作过后有多少不同的颜色序列。\(n,k\le2000\)。Sol先将修改的球当成一种新的颜色。注意到一个性质，假设最终颜色序列一个前缀的第\(i\)个

这里函数采用两个参数n和k，并返回二项式系数C(n,k)的值。 例子： 输入：n=4和k=2输出：6解释：4C2等于4!/(2!*2!)=6输入：n=5和k=2输出：10解释：5C2等于5!/(3!*2!)=10        在本文中，我们讨论了O(n*k)时间和O(k)额外空间算法。C(n,

这里函数采用两个参数n和k，并返回二项式系数C(n,k)的值。 例子： 输入：n=4和k=2输出：6解释：4C2等于4!/(2!*2!)=6输入：n=5和k=2输出：10解释：5C2等于5!/(3!*2!)=10        在本文中，我们讨论了O(n*k)时间和O(k)额外空间算法。C(n,

快速傅里叶变换(FFT)详解原文链接：快速傅里叶变换(FFT)详解-自为风月马前卒-博客园(cnblogs.com)目录前言多项式系数表示法点值表示法复数向量圆的弧度制平行四边形定则复数运算法则单位根单位根的性质快速傅里叶变换快速傅里叶逆变换理论总结

第13届山东省icpc省赛vp总结：2024/4/4赛时：7/12：ABDGIJLhttps://codeforces.com/gym/104417最近开始康复训练，和昊哥vp了一场省赛。前期签到蛮顺利，基本1个多小时就出了5题，然后卡在了E，后面B的实现也弄了蛮久，好在过了J题，vp在省内应该是可以排到前30

Day1考试。T1是神秘构造题，让我们构造一个双射\(f\)，使得\(A\subseteqf(A)\)，其中\(|A|=n-1,|f(A)|=n\)。两者元素均在\([1,2n-1]\)之间。然后好像用Raney引理就可以构造出一个双射：假设\([1,2n-1]\)是一个环，然后假设选过的值是\(+1\)，没选过的是\(-1\)，这个序列的最后

Problem-1929E-Codeforces无意看一眼标签是\(dp\)就一直朝树形状压\(dp\)的方向想了一年，发现不是树形\(dp\)设\(dp_S\)为完成集合\(S\)内的限制所需要的最少边数把每一对顶点的路径上每条边的值都状压，表示添加这条边可以实现的限制有哪些，记为\(b_i\)因

ARC058F考虑背包，记\(f_{i,j}\)表示考虑前\(i\)个串，取出长为\(j\)的最小串。由于涉及字典序比较，时间复杂度为\(\mathcalO(nk^2)\)。字典序比较不同于计算式比较，找到\(LCP\)后第一位即可得出结果。考虑仅保留能转移到\(f_{n,k}\)的\(f_{i,j}\)。对于\(f_{i,j1},f

题目描述组合数\(C_n^m\)表示的是从\(n\)个互不相同的物品中选出\(m\)个物品的方案数。举个例子，从\((1,2,3)\)三个物品中选择两个物品可以有\((1,2)\)，\((1,3)\)，\((2,3)\)这三种选择方法。根据组合数的定义，我们可以给出计算组合数\(C_n^m\)的一般公式：\[C_n^m

[语言月赛202312]NK题目描述给定两个正整数\(N,K\)，请你统计符合以下条件的正整数\(x\)的数量：\(1\leqx\leqN^N\)。\((x\bmodK)\)是\(N\)的倍数。\(x\)的个位是\(N\)。\(x\bmodK\)代表\(x\)除以\(K\)的余数，例如\(7\bmod3=1\)。输入格式输

格路径计数基础格路径计数问题：格路径上从\((0,0)\)走到\((n,m)\)只能向上或向右走，方案数。显然一共走\(n+m\)次，选出任意\(n\)次向上走方案数就是\(\binom{n+m}n\)。有限制格路径计数下面说的限制都是不接触到某条线的限制，若题目要求不超过，可以依次\(+1/-1\)。单

前言洛谷唯一的题解似乎是\(O(nk^2)\)的，怎么卡过去的orz这里提供一种与AT官方题解时间复杂度相同的\(O(nk)\)做法。Solution题意很显然，就不解释了。一眼丁真，考虑数位dp。设\(dp_{i,j}\)表示做到第\(i\)位，不同的个数有\(j\)种的方案数。显然有转移方程：\(dp_{i

P9751[CSP-J2023]旅游巴士本题主要的难点在于到达和离开景区的时间都必须是\(k\)的非负整数倍以及每条道路均设置了一个“开放时间”\(a_i\)。对于第一个限制，只需要拆点，将每个点拆成距离\(\bmodk=0\simk-1\)。对于第二个限制，发现求的是最小值，答案具有二段性，可二分。

CF1451SubtractorDivide显然如果为偶数那么我们将它变到\(2\)再\(-1\)即可如果为奇数我们先\(-1\)再转化为偶数的情况即可对于\(n\le3\)进行特判#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'#defineinlinline#defineebemplace_back

看了题解才悟了，我还是太菜了。solution要求\[\left(\sum_{i=0}^\inftyC_{nk}^{ik+r}\right)\bmodp\]这个形式很像生成函数吧。我们套用生成函数：\[G(x)=\sum_{i=0}^{\infty}\begin{pmatrix}nk\\i\end{pmatrix}x^i\]所求即为\[\sum_{i\bmodk=r}[x^i](1+x)

求图的所有生成树边权和\(k\)次方之和，\(n,k\le50\)。Sol:展开\(k\)次方后会得到\(\sum{k!\overw_1!w_2!...w_{n-1}!}\prode_i^{w_i}\)之类的式子，你发现给每条树边设个生成函数\(f_i(x)=e^{e_ix}\)，答案就是\(k![x^k]\prodf_i(x)\),于是你用矩阵树，带\(1\simnk+1\)

前置知识二项式定理\[(x+y)^n=\sum_{i=0}^n\binomnix^iy^{n-i}\]组合恒等式\[k\times\binomnk=n\times\binom{n-1}{k-1}\]题解先不管取模的事情。考虑把\(f(k)\)中次数相同的项拿出来，则原式可化为：\[Ans=a_0\sum_{k=0}^nx^k\times\binomnk

剑指Offer24.反转链表题目说明定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。解题思路1：栈解题思路2：递归如果从后往前看的话，其实可以这样理解。如果当前处于nk，那么就另nk.next.next=nk，并且将nk.next指向空即可。处理完之后，以nk为头节点的链表其

食物链TimeLimit:1000MSMemoryLimit:10000KTotalSubmissions:56297Accepted:16500Description动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B，B吃C，C吃A。现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种

洛谷传送门AtCoder传送门考虑期望转计数，方案数显然是\(n!\)（第\(i\)次操作有\(n-i+1\)个人可供选择），所以问题转化为求所有方案的代价之和。考虑倒着做，变成先放一个人，然后依次放\(n-1\)个人，每次放的这个人可以让左边的人的\(S\)变成R，代价是他与他左边的人的距离，

Thermodynamics---PVDiagram我们这里主要讨论上面四种PV图的\(\DeltaU,Q,W\),其中\(\DeltaU\)是系统的内能，\(Q\)是系统吸收的能量，\(W\)是外界对系统做的功，我们在理想单原子气体上面讨论。Preliminaries我们一般把内能\(U\)看做温度和体积的函数，即\(U=U(V,T)\),所以\(U\)