涨姿势

• nth_element() 函数可以在平均线性的时间内弄出一个数组内第 $k$ 大的元素放在第 $k$ 个位置上（注意使用方法：nth_element(first,nth,last)）。
• 注意：这么用的时候，假设调用 nth_element(a+1,a+6,a+10)，则排好序的是第6个（而不是第5个），所以中间那个数一定不要写+1！

• ---

  考虑一下子集卷积代码：

• ```
  For(i,0,n){
  For(s,0,len-1){
  For(j,0,n){
  tc[i][s]=(tc[i][s]+1llta[j][s]tb[i-j][s]%mod)%mod;
  }
  }
  }

实测 $n=20$ 跑了 18.36s。/jk（主要时间花在这里）* 改成酱紫：* ```For(i,0,n){    For(j,0,n){        For(s,0,len-1){            tc[i][s]=(tc[i][s]+1ll*ta[j][s]*tb[i-j][s]%mod)%mod;        }    }}

时间变为 6.56s。/jk /fad

• 听说是 cache 友好还是什么的，参考这里
• P.S. 在 luogu 上是 T 与 AC 的区别，但是在 loj 上仅仅是 1s 的区别
• C++14 的速度和 C++20 的速度有着极大的差距，实测 CF960G 中前后两次的代码是相同的，用数据进行测试，C++14 10s，C++20 1s O(∩_∩)O
• dp 如果被卡常，可以仔细看一看 i,j,k 的循环范围，能缩的尽量缩，例如 For i=1..n j=1..n j=1..n 变成 For i=1..n j=1..i k=1..j 就快了6倍了（（
• 多项式 sin 和 cos 不要写泰勒公式，利用 $e^{ix}=i sin (x)+cos (x)$ 和 $e^{-ix}=-i sin (x)+cos (x)$，可以解得 $sin(x)=frac{1}{2i}(e^{ix}-e^{-ix}), cos(x)=frac{1}{2}(e^{ix}+e^{-ix})$，其中取 $i=g^{(P-1)/4}$ 即可~_~
• 时间复杂度与（动态的）状态数有密切关系的 dp，开一个 vector，可以考虑不弄一个 unordered_set 查重，而是采取 if(vec.size()>=5e5) sort(vec.begin(),vec.end()) 然后遍历的同时查重的方式
• 组合意义推柿子时，如果容斥发现一个状态算出来答案是 $1over 2$ 之类的，不要惊慌，这有可能是容斥多余出来的，会与其他项消掉！
• 快速对 [-mod,mod-1] 之间的数取模：

• void qmo(int& x)
{
x+=(x>>31)&mod;
}

• 同时需要记录最小值及其位置并进行更新时，可以 make_pair 然后更新，代码简洁

• cout 输出一行整数居然比 printf 快 10 倍！！1
• 看懂异或和乘法之类的结合，就要想到这玩意一定是分别算出来，不是推性质啊。。。
• 如何对一个 vector 去重： Op[i].erase(unique(Op[i].begin(),Op[i].end()),Op[i].end());
• 神 min 技巧：min({a,b,c,d,e,f})

原文链接: https://www.cnblogs.com/Charlie-Vinnie/p/15816471.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍