[OI wiki](https://oi-wiki.org/dp/opt/quadrangle/#%E5%88%86%E6%B2%BB)上说每个决策点最多计算两次，我画图了一下感觉限制有点复杂，求证明。

在讨论《此题思路》回复：

@[wangkaiwei](luogu://user/1374349)https://www.luogu.com.cn/article/x0l31ikv 我的贪心是这样的

rt

rt,这个肯定是越小越好。 题解代码 ```cpp for(int j=1;j<=P;j++) { for(int i=1;i<=V;i++) { for(int k=0;k<i;k++) { dp[i][j]=min(dp[k][j-1]+w(k+1,i),dp[i][j]); } } } ``` 第4行，写<=会更…

看了好久都不知道哪儿错了 ```cpp #include using namespace std; int a[500001],q,t,x,y; int main(){ cin>>q; while(q--){ cin>>t>>x>>y; if(t==1)a[x]+=y; else{ int ans=0; for(int…

在讨论《GCC 发力了》回复：

甚至比题解某些正解跑得都快

在讨论《求初二小四门开卷如何备考》回复：

不过这个确实~~用脚考~~，我当时一遍弄OI一遍备考都考了接近满分。

在讨论《求初二小四门开卷如何备考》回复：

@[Stars_visitor_tyw](luogu://user/941575)我们是闭卷的，但是我觉得下面的内容可以参考下： - 刷题 - 刷卷 - 大题练习语言表达，这个多抄几遍答案自然就会了

[$$Ans=2\sum_{d=1}^{n}\varphi(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor-nm$$](https://www.luogu.com.cn/article/c3ocj372) 这直接预处理欧拉函数然后直接算不就可以了吗？

在讨论《关于本题测试数据》回复：

不加入原数据吗？

在讨论《(f*g)(n) 是什么意思》回复：

哦谢谢，~~看定义没看到~~

rt bdfs bingfs 无果 就是狄利克雷卷积那个式子里的

my code ```cpp #include #include #include #define int long long using namespace std; int read(){ int k=0,f=1; char c=getchar(); while(c '9'){ if(c=='-')f=-1; c=…

在 [link](https://www.luogu.com.cn/article/fu4e9jm6) 中，提到 ```txt 令sum[i]表示切断i的子树中所有询问点的最小代价之和，并且你不能直接切掉i，再令mi[i]表示i到1号点的路径中最小的边权，那么我们可以得到这样一个转移方程 sum[i]=sigma(mi…

在讨论《虚树的在线 Lca O(n) 算法》回复：

@[yinqf](luogu://user/673730) 哦，那是的。

题解说栈建虚树是O(n)的，但是难以见得 Lca 的 O(n) 算法。 是不是指的是建树算法瓶颈是 O(n) 虽然用 4Russias 算法确实可以做到 O(n)

在讨论《洛谷 2025 年鉴》回复：

洛谷可能会变质，但是绝不会倒闭！

装 set map 之类的，总感觉优不到哪去，感觉 26 的常数又有点大了。

如果这样的话，第一篇题解面对如下数据会输出 3，但是按照正常理解，应该是 5 ```cpp 4 1 2 4 2 4 1 1 4 5 ```

[link](https://www.luogu.com.cn/article/8cy32i00) “ 然后进入要修改的主席树， 再按照主席树修改的操作改就结束啦~ ” 为什么主席树能修改，这里指的是动态普通权值线段树吗

在讨论《求神秘数据结构题做法》回复：

@[cyq32ent](luogu://user/435347) 我有一个单次修改 $O(n)$，查询$O(n\log k)$ 的精妙做法

rt，每个完全二叉树的根节点都是父子关系为左儿子的节点。 这是否是一颗树是左偏树的充要条件 

在讨论《求助A(2^n-1,i-1)怎么求》回复：

而且按理说 $a_i=A_{2^n-1}^{i}\bmod p$ 到了 $2^n-1\ge p$ 的时候应该为 $0$，但是这输出并非 $0$，我怀疑这 $a_i$ 应该不是这个意思。 ```cpp cin>>n>>m; int tot=fpow(2,n)-1; a[0]=1; for(int i=1; i<=m; i…

在讨论《求助A(2^n-1,i-1)怎么求》回复：

@[ini2015_____](luogu://user/1423269)那这个上下两行输出怎么不一样诶 ```cpp #include #define int long long using namespace std; const int p=1e9+7; int fac(int x){ int res=1; fo…

在讨论《求助A(2^n-1,i-1)怎么求》回复：

@[ini2015_____](luogu://user/1423269) $a_i=A_{2^n-1}^{i-1}\times (2^n-i)$ $a_i=\frac{(2^n-1)!}{(i-1)!}\times (2^n-i)$ $a_i=(2^n-i)\Pi_{j=i}^{2^n-1}j$ $A^i_{2^n-…

根据题解代码可知式子： 令 $a_i=A^{i}_{2^n-1}$ 则 $a_0=1,a_i=a_{i-1}\times (2^n-1-i+1)$ 但我不会证。 code: ```cpp int main() { cin>>n>>m; int tot=fpow(2,n)-1; a[0]=1; for(int i=1;…

在讨论《求算((2^n)!)%p,p=1e8+7的O(n)及以下复杂度算法》回复：

@[sto_clx_orz](luogu://user/1069533)那前面那一些也是 p 数量级的啊，要算 p 次

在讨论《求算((2^n)!)%p,p=1e8+7的O(n)及以下复杂度算法》回复：

@[sto_clx_orz](luogu://user/1069533)thx ~~我是弱智~~

rt $2^n! \bmod p$

在讨论《求组合题单》回复：

@[zsjaaaxy](luogu://user/1037841)[官方题单即可](https://www.luogu.com.cn/training/217#problems)，亲测质量还不错