设 $ x1_i $ 表示到`i`的最后一段1的和的期望，$ x2_i $ 表示到`i`的最后一段1的平方和的期望,$ x3_i $ 表示到`i`的最后一段1的立方和的期望，$ f_i $ 表示前项 $ i $ 的答案，为什么不能 $$ x3_i=p_i(x3_{i-1}+3x2_{i-1}+3x1_{i-1}+1)…

```cpp #include using namespace std; int n; const int N=205,inf=0x3f3f3f3f; #define pii pair #define fi first #define se second pii a[N]; pii f[2][2*N][2*N];//前…

本人在突破50pts大关后屡次90,95分，虽然有longdouble的加持但仍旧先后WA了：15&17，16，11，12（修改了拆的系数），但同为5次FFT，为什么我的代码困于精度问题而非时间，求高人提升精度🙏（或找出原因 ```cpp #include using namespace std; struct Cp…

```cpp #include using namespace std; #define uint int int n,k,t; const int N=1e7+5; uint pw(uint x,int k){ uint ans=1; while(k){ if(k&1)ans=ans*x; k>>=1,x=x*x;…

```cpp #include #define int long long using namespace std; const int N=2e4+5; int n,q; int a[N],re[N]; #define pii pair #define fi first #define se second pii p…

在讨论《O(n)T3求hack》回复：

@[SleepWithMiku](luogu://user/684191)我觉得是mnDP， $ f_{u,i}=max(f_{v,i-1}+sum{g_v}-g_v+i+1),g_u=max(f_{u,i}) $ ;但过不了样例2，求hack

在讨论《O(n)T3求hack》回复：

@[SleepWithMiku](luogu://user/684191) 我觉得是mnDP，f_{u,i}=max(f_{v,i-1}+sum{g_v}-g_v+i+1),g_u=max(f_{u,i});但过不了样例2，求hack

在讨论《O(n)T3求hack》回复：

我在他旁边

在讨论《O(n)T3求hack》回复：

@[SleepWithMiku](luogu://user/684191) 他过了前两个样例，后面记不住了

在讨论《动开线段树92pts求条》回复：

@[like_garbage](luogu://user/762555)我右移了1位，但求条orz

```cpp #include using namespace std; #define int long long const int N=1e5+5; const int P=1; struct sgt{ int ls,rs,sz; }t[60000005]; int id=1,n,tn=1 =k)return g…

```cpp #include using namespace std; const int N=1e5+5; const int P=1e7+5; struct sgt{ int ls,rs,sz; }t[5000005]; int id=1,n,tn=1 =k)return getnum(l,(l+r)/2,t[u…

[rt](https://www.luogu.com.cn/article/vpr10a35)，数环的奇偶，判相等，题解里没有同思路，次优解。 @[xmyzwls](luogu://user/14) @[chen_zhe](luogu://user/8457)

这道题有点像数字华容道，可以算出两个网格能否能够转化为顺序。 首先，能够任意交换3个数的位置，不能任意交换2个数的位置。 那么则说明能将奇数个数依次替换，偶数则不行，也可以交换偶数次偶数个数。 也就是可以去找所有的环中点数为偶数的环的数量，若两个网格偶环数量的奇偶性相同则可以转换。 可以在最初把`0`推到右下角。 ``…

在讨论《T1咋做》回复：

@[a_cow_of_FJ](luogu://user/1391214)最小的必不选，用堆维护最大和次大的差就行吧

n方过十万后想写正解。样例能过，求调 ```cpp #include using namespace std; #define int long long #define pii pair #define fi first #define se second const int N=2e5; const int S=5…

在讨论《60分求调，玄关》回复：

@[xyx_AK_ALL](luogu://user/1727652) 注释处为新添加代码 ```cpp #include #define int long long using namespace std; const int dGx[4]={-1,1,0,0}; const int dGy[4]={0,0,-1,1…

在讨论《60分求调，玄关》回复：

@[xyx_AK_ALL](luogu://user/1727652) a[x][y]!='X' && a[x][y]!='#'); 这一句中'X'和'#'的地位没有区别，实际依题意走到'X'会失败，走到'#'会被挡住

在讨论《45玄关》回复：

然后f()中若有0，返回0，(可能一个1也没有)

在讨论《45玄关》回复：

首先数组开小了o，开[12]是0~11，建议多开几个

在讨论《优先队列30求调》回复：

@[a88662347](luogu://user/1884643) n=1e7优先队列会TLE 注意到a≤1e5，可以用桶排序，从前向后边扫边合并，超过桶范围的用vector存一下，桶扫完再扫vector就可以了

## 倍增 lca 题解 题目要求每条边最多走两次，$s$ 中的点必须按顺序被遍历，问从每一个点出发能否按照要求遍历 判断是否有一种行程满足要求，先从 $s_1$ 按 $s_i$ 顺序遍历一遍，当搜索到 $u$ 时，求 $s_i $ 与 $u$ 的 $lca$。若 $lca$ 为 $u$，则从 $s_i$ 倍增到 $u…

在讨论《站外题求助》回复：

@[Orange0628](luogu://user/980202)@[wyp20130701](luogu://user/1242208)发不了

**题目描述**\ 已知接下来$n$秒的宇宙射线强度，第$i$秒的宇宙射线强度为$a_i$。众所周知，出题是一件很需要灵感的事情，所以只有在一段时间内最强射线与最弱射线的差值（即极差）恰好等于$k$时，出题人才能出出题来。 出题人不希望自己的出题思路被打断，因此出题人每次只会在可以用来出题的时间中选择一段连续的时间进行…

```cpp #include using namespace std; int n,k,p; priority_queue >pq; int nxt[500005],f[500005],a[500005],vis[500005]; int main(){ scanf("%d%d%d",&n,&k,&p); for(i…

在讨论《0分但过样例，求调》回复：

@[ini_____](luogu://user/1423269)题解区的结构体都不想看

在讨论《0分但过样例，求调》回复：

@[ini_____](luogu://user/1423269)而且已经学好久了

在讨论《0分但过样例，求调》回复：

@[ini_____](luogu://user/1423269)包是自己写的

```cpp #include using namespace std; int n,q,m; int t[400005]; int lzt1[400005];//* int lzt2[400005];//+ void upd1(int l,int r,int mid,int u){ if(lzt1[u]!=1&&l!…

在讨论《19分，过样例求调》回复：

已经A了，感谢