摘要: 这段时间只放板子了。为什么不写题解?答:rt。 阅读全文
posted @ 2022-01-10 16:35 T_X蒻 阅读(12) 评论(1) 推荐(0) 编辑
摘要: tarjan 全家桶 关于tarjan 它太强了 CCCOrz dfs树&low dfs树:在图上做不重复经过同一点的dfs,经过的边与点形成一棵树。于是图上所有点都被这棵树包含,一部分边被包含。称被包含的点叫树边,其他边叫回边。整个图就是dfs树,由于是由dfs得到。所以dfs树有非常强的性质,所 阅读全文
posted @ 2022-01-10 16:56 T_X蒻 阅读(7) 评论(0) 推荐(0) 编辑
摘要: #include<bits/stdc++.h> using namespace std; const int MM=400005; int dfn[MM],low[MM],dfc,cnt,in[MM],tot,v[MM],vis[MM],siz[MM],n,m,V,U; long long ans; 阅读全文
posted @ 2022-01-10 16:37 T_X蒻 阅读(4) 评论(0) 推荐(0) 编辑
摘要: 这段时间只放板子了。为什么不写题解?答:rt。 阅读全文
posted @ 2022-01-10 16:35 T_X蒻 阅读(12) 评论(1) 推荐(0) 编辑
摘要: #include<bits/stdc++.h>//树状数组二分 using namespace std; int q,b,s,t[1000],k,sum1[1000],sum2[1000],n=10; void add(int p,int k) { for(int i=p;i<=n;i+=i&-i) 阅读全文
posted @ 2022-01-03 11:51 T_X蒻 阅读(9) 评论(0) 推荐(0) 编辑
摘要: 斜率优化 直接看例题 例题:P3195 解析 转移方程很简单: 这里$f[i]$表示前$i$个物品的最优代价。$a$为$c$(如题目)的前缀和。 \[ a[i]=\sum_{j=1}^i c[j] \\ f[i]=\min(f[j]+(a[i]-a[j]+i-j-1-L)^2) \] 令$g[i][ 阅读全文
posted @ 2021-12-29 15:48 T_X蒻 阅读(36) 评论(2) 推荐(0) 编辑
摘要: 多项式除和取余 \[ F(x)=Q(x)G(x)+R(x) \] 已知$n$次的$F(x)$和$m$次$G(x)$求商$Q(x)$和余数$R(x)$,要求$Q(x)$次数为$n-m$,$R(x)$次数小于$m$ 以下$inv(x)$表示$x$的逆元 首先考虑整除的情况 \[ Q=F*inv(G) \ 阅读全文
posted @ 2021-12-27 16:58 T_X蒻 阅读(23) 评论(0) 推荐(0) 编辑
摘要: 多项式求逆元 已知一度数为n的多项式$A(x)$。 \[ A(x)B(x)\equiv1\pmod {x^n} \] $B(x)$即为$A(x)$的逆元。 多项式的除法、$\exp$和$\ln$都是基于多项式求逆的。 通常用倍增法处理多项式求逆问题。 开始推式子…… \[ \begin{aligne 阅读全文
posted @ 2021-12-27 16:03 T_X蒻 阅读(15) 评论(0) 推荐(0) 编辑
摘要: #include<bits/stdc++.h> using namespace std; const int MM=100005; int u,v,w,c,tmp,n,m,s,t,tot=1,flow,cost,nxt[MM],to[MM],fl[MM],cs[MM],dis[MM],head[MM 阅读全文
posted @ 2021-12-24 15:35 T_X蒻 阅读(7) 评论(0) 推荐(0) 编辑
摘要: #include<bits/stdc++.h> using namespace std; const int MM=4e5+5,inf=0x3f3f3f3f; int n,m,s,t,tot=1,a; int nxt[MM],head[MM],to[MM],w[MM]; int h[MM],e[MM 阅读全文
posted @ 2021-12-24 15:29 T_X蒻 阅读(10) 评论(1) 推荐(0) 编辑
摘要: NTT 先学习FFT 由于FFT是使用复数运算,精度并不好,而且也无法取模,所以有了NTT(快速数论变换)。 建议先完全理解FFT后再学习NTT。 原根 NTT使用与单位根性质相似的原根来代替单位根。 定义:设$m$是正整数,$a$是整数,若$a$模$m$的阶等于$φ(m)$,则称$a$为模$m$的 阅读全文
posted @ 2021-12-22 15:07 T_X蒻 阅读(30) 评论(0) 推荐(0) 编辑