【20联赛集训day10】排列一个长度为\(n\)的排列，每次操作删除所有存在相邻的数字比它更大的数字，问执行\(k\)次操作后剩下恰好一个数的排列方案数。首先因为每次删除至少删一半的数字，所以最多删\(\log\)次。对于一个排列，我们可以发现把序列按最大值劈开，左右两边互不干扰，成

题TLE95#include<iostream>#include<map>#include<ext/pb_ds/assoc_container.hpp>#include<ext/pb_ds/hash_policy.hpp>#definelllonglong#pragmaGCCoptimize(5)#pragmaGCCoptimize("Ofast")constllN=5e3+10,p=1e9+7;

口吃题目描述Zaoly要讲一句话，这句话有n个字，他要一个字一个字讲出来。奈何Zaoly口吃：讲到第1个字时，下一个要讲的字有$\frac{a_1}{a_1+b_1}$的概率前进到第2个字，有$\frac{b_1}{a_1+b_1}$的概率仍是第1个字。讲到第$i$$(2\leqi\leqn−1)$个字时，下一个要讲

原题链接：https://www.luogu.com.cn/problem/P1226题意解读：快速幂模版题。解题思路：1、分治法要计算a^b，可以对b分情况讨论：如果b是偶数，即b=2t，a^b=a^t*a^t如果b是奇数，即b=2t+1，a^b=a*a^t*a^t很容易用递归实现100分代码：#include<bits/stdc++.h>usingnamespa

洛谷P3469BLO-Blockade题意给定一张无向图，求每个点被封锁之后有多少个有序点对\((x,y)(x\ney,1<=x,y<=n)\)满足\(x\)无法到达\(y\)。思路使用Tarjan求出割点，有以下几种情况。当前点不是割点，答案为\(2\times(n-1)\)，即该点与其他所有点不连通。当前点是割点，答案

题目链接点击打开链接题目解法会不了\(egf\)/ll我们把贡献变成\(\prod\limits_{j\neqi}a_j=\prod\limits_{j=1}^na_j-\prod\limits_{j=1}^n(a_i-[i=j])\)即答案为一开始的乘积\(-\)\(k\)次操作之后所有数乘积的期望因为有顺序，所以用\(egf\)的形式表示最后乘积的期

预设型DP《美好的一天》--青春学概论한잔술에취해잠긴목엔沉醉于一杯酒갈라지는목소린다시带着沙哑的嗓音두잔자기전엔기분좋음入睡前饮下第二杯让心情愉悦알수없는세상에빠져陷入不可预知的世界세잔또네잔술에빠진又沉醉于第三杯第四杯세상

\(\text{Link}\)题意给你一个长为\(n\)的序列\(a_{1\dotsn}\)，定义一条边\((u,v)\)的权值为\(a_u+a_v\)。对于一张图，定义其权值为包含的所有边的权值乘积。求所有\(n\)个点的有标号基环树的权值之和。对\(998244353\)取模。\(n\le10^3\)。思路非常厉害的题，zky倾

CF1503E2-Coloringcjx组合强。思路观察一下题目，不难发现只有当黄色形成如下的单峰时才合法。（染错色了，将就一下）其中两座峰的峰顶高度相加等于\(m\)，为了方便统计，我们钦定右边的峰一定在左峰下方的行出现，最后答案乘以二就是最终方案。发现对于每一边是两个最长不下降子序列

思路：考虑往直径方向想，设直径的长度为\(d\)。首先可以注意到一个性质：每次操作最多只会覆盖住直径的\(2\)个点，那么答案的下界即为\(\lceil\frac{d}{2}\rceil\)。分类讨论一下。若\(d\)为奇数，则存在唯一的一个直径中心\(u\)：那么答案为\((u,0),(u,1),\cdots,(u,\l

感觉没啥好说的，只要你知道扩展欧拉定理的式子就很trivial的一个题幂塔类的问题都考虑用扩展欧拉定理降幂，则每往指数上操作一层复杂度模数就会从\(m\)变为\(\phi(m)\)根据经典结论可知，该过程在大约\(\logm\)次操作后就会让模数变为\(1\)，此时后面的部分就无需再计算了不

P1350车的放置-洛谷|计算机科学教育新生态(luogu.com.cn)非递推做法，对于这个题，这个图形之间统计很麻烦，由此我们可以把它分成两个矩形。如直接沿\(b\)边切割。但这样我们发现还是不好统计，因为左边矩形会受到右边不一定的限制，于是沿着\(b,c\)边再次切割，分成三个矩形，从上

比较有意思的Counting，想到横竖两种骨牌的独立性就很好做了考虑如果枚举最后放了\(x\)块横着的骨牌，\(y\)块竖着的骨牌，直接考虑它们的摆放不方便，不妨转化一下在所有空余的行中，选择\(x+2y\)行，且满足其中有\(y\)对相邻的行；在所有空余的列中，选择\(2x+y\)列，且满足其中有\(x

前言CodeforcesRound836(Div.2)C.AlmostAllMultiples这题挺妙的。很容易发现$n%x==0$时无解。让\(p[x]=n,p[1]=x,p[n]=1\)就是一个可行解。但此题要求字典序最小，我们以\(8,2\)为例。现在的序列：28345671字典序最小的序列：24385671可以发

D.XORificatorYouaregivenabinary(consistingonlyof0sand1s)$n\timesm$matrix.YouarealsogivenaXORificator,usingwhichyoucaninvertallthevaluesinachosenrow(i.e.replace0with1and1with0).Acolumninthematrixisconsider

题意：计算满足如下条件的带标号有根树数量：这棵树一共有\(n\)个节点。每个节点都有一个整数权值，且在区间\([1,m]\)内。每个节点的权值都不大于其父节点的权值。\(n,m\le400\)思路：好题。对于这种计数问题，肯定第一眼会想到\(dp\)，我们设\(f_{n,m}\)表示\(n\)个点

Alink模拟整个过程即可。点击查看代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;signedmain(){ inth; cin>>h; intday=1ll,g=0ll; while(g<h){ g+=(1ll<<day); day++; } cout<<day; return

题目链接点击打开链接题目解法不考虑第\(a_{r,c}=v\)的限制怎么求？我们把条件形式化一下，发现\(k\)个区域的颜色可以表示成轮廓线的形式，即第\(i-1\)条到第\(i\)条轮廓线之间的格点颜色为\(i\)问题变成找到\(k-1\)条互不穿过的路径，起点为\((1,m)\)，终点为\((n,1)\)

题解：CSP-S2020]函数调用一句话题意：给定一个有初始值的序列，支持如下三种操作：1、单点加2、全局乘3、递归某些操作1、2、3求最终的序列。标签：topsort，动态规划，转化贡献统计（集中贡献），主客翻转关于topsort：部分分里的树结构基本上直接暗示了正解要使用topsort，而且本来函

题意：Yelekastee是U国著名的考古学家。在最近的一次考古行动中，他发掘出了一个远古时期的密码箱。经过周密而严谨的考证，Yelekastee得知密码箱的密码和某一个数列\(\{a_n\}\)相关。数列\(\{a_n\}\)可以用如下方式构造出来：初始时数列长度为\(2\)且有\(a_0=0,a_1

逆元若\(i\cdotx=1\)，则\(i^{-1}=x\)。递推求乘法逆元\[令模数为p,正整数i,a=\lfloor\frac{p}{i}\rfloor,b=p\operatorname{mod}i,且b\ne0。\\a\cdoti+b=p\\\Downarrow\\a\cdoti+b\equiv0(\operatorname{mod}p)\\\frac{i}{b}+\frac{1}{a}\equiv0(\o

洛谷P6692出生点题意简述\(n\)行\(m\)列构成\(nm\)个格点，在其中指定\(k\)个障碍点。每行、每列之间的距离为\(1\)，每次任意选取两个非障碍点，计算这两个点的曼哈顿距离，求所有选法的距离之和。分析由容斥原理，答案为「任意两点之间的距离之和」\(-\)「每个障碍点到其他

题目如下：[NOIP2002普及组]过河卒题目描述棋盘上AAA点有一个过河卒，需要走到目标BB

1LL、2LL即是longlong类型的1，21LL常常使用在当临时数据超出int型的计算中（整型数据范围是-2^31~2^31-1）例如当计算intnum=100000*100000/100000;时，正确结果是100000，但由于100000*100000产生的临时数据超过了int类型的范围，所以编译器最终的运算结果14100是错误的intn

题意求有多少种长度为\(N\)的满足以下条件的序列。是一个\(1\simN\)的排列。至少进行\(K\)次操作后，该序列才含有一个元素。\(N\le1000\)Sol首先因为序列是一个排列，所以操作次数不会太多。操作次数大概在\(\logN\)的级别。不难注意到对于一个数列，剩下的只