高精度类
struct bint : Vi {
bint(int n=1) { resize(n); }
void clr() { while( size() > 1 && !back() ) pop_back(); }
friend istream& operator >> (istream &io,bint &a) {
string s; io>>s;
a.clear(); rFor(i,sz(s)-1,0) a.pb(s[i]-'0');
return io;
}
friend ostream& operator << (ostream &io,const bint &a) {
rFor(i,sz(a)-1,0) cout<<a[i];
return io;
}
friend bool operator < (const bint &a,const bint &b) {
if( sz(a) < sz(b) ) return 1;
rFor(i,sz(a)-1,0) if( a[i] != b[i] ) return a[i]<b[i];
return 0;
}
friend bint operator - (bint a,const bint &b) {
Rep(i,0,sz(a)) {
if( a[i] < b[i] ) --a[i+1], a[i] += 10;
a[i] -= b[i];
}
return a.clr(), a;
}
friend bint operator * (const bint &a,const bint &b) {
bint c(sz(a)+sz(b)+1);
Rep(i,0,sz(a)) Rep(j,0,sz(b)) c[i+j] += a[i] * b[j];
Rep(i,0,sz(c)) if( c[i] >= 10 ) c[i+1] += c[i]/10, c[i] %= 10;
return c.clr(), c;
}
};
分数类
组合数学
线性代数
矩阵乘法
凸包
求 \(\max_{i}\{kx_{i}+y_{i}\}\)。\(x_{i},y_{i},k\) 为
int
对 \((x_{i},y_{i})\) 建上凸包，查询斜率为 \(-k\) 的直线的最大截距
- 静态建
struct Vec {
LL x,y; Vec(LL x=0,LL y=0):x(x),y(y){}
bool operator < (const Vec &rhs) { return x!=rhs.x ? x<rhs.x : y<rhs.y; }
Vec operator - (const Vec &rhs) { return {x-rhs.x, y-rhs.y}; }
LL operator & (const Vec &rhs) { return x*rhs.y-y*rhs.x; } // 叉乘
};
static Vec s[N]; int t = 0;
sort(all(p));
for(auto i : p) {
while( t > 1 && (s[t]-s[t-1]&i-s[t-1]) >= 0 ) --t;
s[++t] = i;
}
-
二分查询
-
双指针查询
sort(all(q),[](int x,int y){return k[x]<k[y];});
int j = 1;
for(int i : q) {
auto f=[&](int j) { return k[j]*s[i].x+s[i].y; };
while( j < t && f(j+1) > f(j) ) ++j;
ans[i] = f(j);
}
拉格朗日插值
\(n+1\) 个点值确定一个\(n\) 次多项式
\[f(x)=\sum_{i=1}^{n+1}y_{i}\prod_{j\ne i}\frac{x-x_{j}}{x_{i}-x_{j}} \] 标签：return,int,LL,数学,Vec,io,operator,模板 From： https://www.cnblogs.com/ft61/p/17950677