模版大全
__Alex866__
·
·
个人记录
提示
- 部分代码又臭又长，请谨慎阅读。
- 最好使用 PgUp 和 PgDn 键浏览。
经典火车头
#include<bits/extc++.h>
//#define ONLINE_JUDGE
#define _INT_TO_LL
#define _CLOSE_SYNC
//#define _USE_FREOPEN
#if 1
using namespace std;
using namespace chrono;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
using ui32=unsigned int;
using i64=long long;
using ui64=unsigned long long;
using i128=__int128;
using ui128=unsigned __int128;
using f64=double;
using f128=long double;
template<typename _Type> _Type __lcm(_Type a,_Type b){
return a/__gcd(a,b)*b;
}
template<typename _Type>
string YN(_Type a,int b=1){
return a?(b&2?"YES":b&1?"Yes":"yes"):(b&2?"NO":b&1?"No":"no");
}
template<typename Array,typename _Type>
void mem(Array &arr,const _Type &value){
typename remove_all_extents<Array>::type typedef ElementType;
fill_n(reinterpret_cast<ElementType*>(&arr),sizeof(arr)/sizeof(ElementType),static_cast<ElementType>(value));
}
template<typename Array>
void clr(Array &arr){
typename remove_all_extents<Array>::type typedef ElementType;
mem(arr,ElementType(0));
}
template<typename Array>
void neg(Array &arr){
typename remove_all_extents<Array>::type typedef ElementType;
mem(arr,ElementType(-1));
}
template<typename Array>
void fmax(Array &arr){
typename remove_all_extents<Array>::type typedef ElementType;
mem(arr,numeric_limits<ElementType>::max());
}
template<typename Array>
void fmax_s(Array &arr){
typename remove_all_extents<Array>::type typedef ElementType;
mem(arr,numeric_limits<ElementType>::max()/2);
}
template<typename Array>
void fmin(Array &arr){
typename remove_all_extents<Array>::type typedef ElementType;
mem(arr,numeric_limits<ElementType>::min());
}
template<typename Array>
void fmin_s(Array &arr){
typename remove_all_extents<Array>::type typedef ElementType;
mem(arr,numeric_limits<ElementType>::min()/2);
}
mt19937_64 _Random(system_clock::now().time_since_epoch().count());
template<typename _Type>
_Type _Rand(_Type l,_Type r){
return uniform_int_distribution<_Type>(l,r)(_Random);
}
template<typename _Type>
void srand(_Type _Seed){
_Random.seed(_Seed);
}
int rand(){
return _Rand(0,RAND_MAX);
}
template<typename _Type,typename _Compare>
using _CPQ=std::priority_queue<_Type,vector<_Type>,_Compare>;
template<typename _Type>
using _GPQ=_CPQ<_Type,greater<>>;
template<typename _Type>
using _PQ=std::priority_queue<_Type>;
template<typename _Key,typename _Type>
using _MM=multimap<_Key,_Type>;
template<typename _Type>
using _MS=multiset<_Type>;
template<typename _Type>
using _P=pair<_Type,_Type>;
template<typename _Key,typename _Type>
using _UM=unordered_map<_Key,_Type>;
template<typename _Type>
using _US=unordered_set<_Type>;
template<typename _Key,typename _Type>
using _UMM=unordered_multimap<_Key,_Type>;
template<typename _Type>
using _UMS=unordered_multiset<_Type>;
template<typename _Type>
using _V=vector<_Type>;
constexpr ui64 HashP=1313131313131313131ull,HashP1=1111111111111111171ull,HashP2=37093201209218101ull,HashP3=3113333333333333333ull,HashP4=4444444444444444409ull,HashP5=370903201209218177ull;
constexpr int mod3=998244353,mod7=1000000007,mod9=1000000009,d4[4][2]={{0,1},{1,0},{0,-1},{-1,0}},d8[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
istream& operator>>(istream& in,i128& a){
a=0;
char ch;
bool fl;
while(isspace((in.get(ch),ch)));
fl=(ch==45?ch=in.get(),1:0);
while(isdigit(ch)){
(a*=10)+=ch^48;
in.get(ch);
}
if(fl){
a=-a;
}
return in;
}
istream& operator>>(istream& in,ui128& a){
a=0;
char ch;
while(isspace((in.get(ch),ch)));
while(isdigit(ch)){
(a*=10)+=ch^48;
in.get(ch);
}
return in;
}
ostream& operator<<(ostream& out,const i128& a){
if(a<0){
out<<'-';
out<<-a;
return out;
}
if(a<10){
out<<char(a^48);
return out;
}
out<<a/10;
return out<<a%10;
}
ostream& operator<<(ostream& out,const ui128& a){
if(a<10){
out<<char(a^48);
return out;
}
out<<a/10;
return out<<a%10;
}
#define y0 __Y0_By_MySelf__
#define y1 __Y1_By_MySelf__
#define yn __Yn_By_MySelf__
#define j0 __J0_By_MySelf__
#define j1 __J1_By_MySelf__
#define jn __Jn_By_MySelf__
#define _FF(_Name,_Begin,_End) for(auto _Name=(_Begin);_Name<(_End);_Name++)
#define _RF(_Name,_Begin,_End) for(auto _Name=(_Begin)-1;_Name>=(_End);_Name--)
#define _FE(_Container,...) for(auto __VA_ARGS__:_Container)
#define _SP(_Digit) fixed<<setprecision(_Digit)
#define _Max(...) max({__VA_ARGS__})
#define _Min(...) min({__VA_ARGS__})
#define tostr(_Name) std::to_string(_Name)
#ifndef ONLINE_JUDGE
void pt(){
cerr<<endl;
}
template<typename _Slipt,typename _End,typename _Type>
void pt(_Slipt,_End end,_Type a){
cerr<<a<<end;
}
template<typename _Slipt,typename _End,typename _Type,typename... _Args>
void pt(_Slipt slipt,_End end,_Type a,_Args ...args){
cerr<<a<<slipt;
pt(slipt,end,args...);
}
template<typename... _Args>
void psp(_Args ...args){
pt(' ',' ',args...);
}
template<typename... _Args>
void pln(_Args ...args){
pt(' ','\n',args...);
}
template<typename _Type>
void __psth(_Type line){
static int cnt;
pt("","","\n-------------------------No.",cnt," Line:",line,"-------------------------\n");
cnt++;
}
#define psth() __psth(__LINE__)
#else
#define pt(...)
#define psp(...)
#define pln(...)
#define psth(...)
#define __psth(...)
#endif
#ifdef _INT_TO_LL
#define int i64
#define INT_MAX LLONG_MAX
#define INT_MIN LLONG_MIN
#endif
using _Pi=_P<int>;
using _Vi=_V<int>;
using _Vpi=_V<_Pi>;
#endif
signed main(){
ifdef _CLOSE_SYNC
cin.tie(0)->sync_with_stdio(0);
endif
ifdef _USE_FREOPEN
ifstream fin(".in");
ofstream fout(".out");
cin.rdbuf(fin.rdbuf());
cout.rdbuf(fout.rdbuf());
endif
return 0;
}
## 随机数（建议背过）
```cpp
mt19937 rd(chrono::system_clock::now().time_since_epoch().count());
卡常 & 函数
卡常小技巧
ull gcd(ull x,ull y){
if(!x){
return y;
}
if(!y){
return x;
}
int t=__builtin_ctz(x|y);
x>>=__builtin_ctz(x);
do{
y>>=__builtin_ctz(y);
if(x>y){
swap(x,y);
}
y-=x;
}while(y);
return x<<t;
}
ll gcd(ll x,ll y){
if(!x){
return y;
}
if(!y){
return x;
}
int t=__builtin_ctzll(x|y);
x>>=__builtin_ctzll(x);
do{
y>>=__builtin_ctzll(y);
if(x>y){
swap(x,y);
}
y-=x;
}while(y);
return x<<t;
}
bool is_odd(ll x){ //奇数
return ~x&1;
}
bool is_odd(ull x){ //奇数
return ~x&1;
}
bool is_even(ll x){ //偶数
return x&1;
}
bool is_even(ull x){ //偶数
return x&1;
}
bool int_greater(int x,int y){ //大于
return((uint)(y)-(uint)(x))>>31;
}
bool uint_greater(uint x,uint y){ //大于
return(y-x)>>31;
}
bool ll_greater(ll x,ll y){ //大于
return((ull)(y)-(ull)(x))>>63;
}
bool ull_greater(ull x,ull y){ //大于
return(y-x)>>63;
}
bool opposite(ll x){ //相反数
return ~x+1;
}
bool opposite(ull x){ //相反数
return ~x+1;
}
int int_abs(int x){
return x^(~(x>>31)+1)+(x>>31);
}
ll ll_abs(ll x){
return x^(~(x>>63)+1)+(x>>63);
}
template <typename T>
void data_swap(T &x,T &y){
x^=y^=x^=y;
}
奇奇怪怪的函数
template <typename T>
double log(T n,T di){
return log(n)/log(di);
}
void printFloatBits(float value) {
unsigned long long bits=*reinterpret_cast<unsigned long long*>(&value);
bitset<sizeof(float)*CHAR_BIT> binary(bits);
for(int i=binary.size()-1;i>=0;i--){
cout<<binary[i];
if(i%8==0){
cout<<' ';
}
}
}
void printDoubleBits(double value) {
unsigned long long bits=*reinterpret_cast<unsigned long long*>(&value);
bitset<sizeof(double)*CHAR_BIT> binary(bits);
for(int i=binary.size()-1;i>=0;i--){
cout<<binary[i];
if(i%8==0){
cout<<' ';
}
}
}
void printLongDoubleBits(long double value) {
unsigned char* bytes=reinterpret_cast<unsigned char*>(&value);
for (int i=0;i<sizeof(long double);i++){
bitset<CHAR_BIT> binary(bytes[i]);
cout<<binary<<" ";
}
}
double test_time(){
LARGE_INTEGER nFreq;
LARGE_INTEGER nBeginTime;
LARGE_INTEGER nEndTime;
QueryPerformanceFrequency(&nFreq);
QueryPerformanceCounter(&nBeginTime);//开始计时
//TODO
QueryPerformanceCounter(&nEndTime);//停止计时
return double(nEndTime.QuadPart-nBeginTime.QuadPart)/(double)nFreq.QuadPart;//计算程序执行时间单位为s
}
void rgb_init(){ //调整控制台颜色
HANDLE hIn=GetStdHandle(STD_INPUT_HANDLE);
HANDLE hOut=GetStdHandle(STD_OUTPUT_HANDLE);
DWORD dwInMode,dwOutMode;
GetConsoleMode(hIn,&dwInMode);
GetConsoleMode(hOut,&dwOutMode);
dwInMode|=0x0200;
dwOutMode|=0x0004;
SetConsoleMode(hIn,dwInMode);
SetConsoleMode(hOut,dwOutMode);
}
void rgb_set(int wr,int wg,int wb,int br,int bg,int bb){
printf("\033[38;2;%d;%d;%dm\033[48;2;%d;%d;%dm",wr,wg,wb,br,bg,bb);
}
void messy(){
srand(time(0));
while(1){
for(long long i=1;i<=rand()%100+1;i++){
int x=rand()%3;
if(x==0){
rgb_set(rand()%256,rand()%256,rand()%256,rand()%256,rand()%256,rand()%256);
cout<<rand();
fflush(stdout);
Sleep(rand()%3);
}
if(x==1){
for(long long i=1;i<=rand()%100+1;i++){
rgb_set(rand()%256,rand()%256,rand()%256,rand()%256,rand()%256,rand()%256);
cout<<(char)(rand()%128);
fflush(stdout);
Sleep(rand()%3);
}
}
if(x==2){
for(long long i=1;i<=rand()%10+1;i++){
rgb_set(rand()%256,rand()%256,rand()%256,rand()%256,rand()%256,rand()%256);
cout<<" ";
fflush(stdout);
Sleep(rand()%3);
}
}
Sleep(rand()%10);
}
for(long long i=1;i<=rand()%3+1;i++){
cout<<endl;
Sleep(rand()%3);
}
}
}
快速幂
ll fastPow(ll a,ll n,ll m){
a%=m;
if(n==0||a==1){
return 1;
}
if(n==1){
return a;
}
ll ans=1,s=a;
while(n){
if(n&1){
ans=ans*s%m;
}
s=s*s%m;
n>>=1;
}
return ans;
}
ull fastPow(ull a,ull n,ull m){
a%=m;
if(n==0||a==1){
return 1;
}
if(n==1){
return a;
}
ull ans=1,s=a;
while(n){
if(n&1){
ans=ans*s%m;
}
s=s*s%m;
n>>=1;
}
return ans;
}
二分
bool chack(/*Something*/){
//TODO
return /*Value*/0;
}
int binarySearch(/*Something*/){
int l=0,r=1e9/*Max*/,mid; //l:满足条件
while(l<=r){
mid=(l+r)/2;
if(chack(/*Something*/)){ //不满足
l=mid+1;
}else{
r=mid-1;
}
}
return r;
}
三分
while(l<=r){
mid=(r-l)/3;
if(check(l+mid)<check(r-mid)){
r-=mid+1e-9;
}else{
l+=mid+1e-9;
}
}
并查集
int fa[1005],rnk[1005];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
x=find(x);
y=find(y);
if(x==y){
return;
}
if(rnk[x]==rnk[y]){
if(rand()&1){
fa[x]=y;
rnk[y]+=rnk[x];
}else{
fa[y]=x;
rnk[x]+=rnk[y];
}
}else if(rnk[x]<rnk[y]){
fa[x]=y;
rnk[y]+=rnk[x];
}else{
fa[y]=x;
rnk[x]+=rnk[y];
}
}
01分数规划
同二分。二分\frac{\sum a_i}{\sum b_i}
数据结构
单调队列
//优先队列用priority_queue
template <typename T>
class monotonicQueueC{
private:
deque<T>dq;
unsigned maxlen;
public:
monotonicQueueC(int len=0):maxlen(len){
dq.clear();
}
void push(T a){
while(dq.size()&&dq.back()>a){
dq.pop_back();
}
dq.push_back(a);
if(dq.size()>maxlen){
while(dq.size()&&dq.size()>maxlen){
dq.pop_back();
}
}
}
void pop(){
dq.pop_front();
}
void print(){
for(auto i:dq){
cout<<i<<" ";
}
}
void init(){
T tmp;
for(unsigned i=0;i<maxlen;i++){
cin>>tmp;
push(tmp);
}
}
};
单调栈
template <typename T>
class monotonicStackC{
private:
deque<T>st;
public:
monotonicStackC(int len=0){
st.clear();
}
void push(int a){
while(st.size()&&st.back()>a){
st.pop_back();
}
st.push_back(a);
}
void pop(){
st.pop_back();
}
void print(){
for(auto i:st){
cout<<i<<" ";
}
}
void init(){
string s;
T tmp;
cin>>s;
while(~sscanf(s.c_str(),"%d",&tmp)){
push(tmp);
}
}
};
树状数组
template<typename T>
struct binaryIndexedTree{
public:
vector<T> tree;
template <typename _T>
_T lowbit(_T x){
return -x&x;
}
binaryIndexedTree(int len=0,int *a=nullptr){
tree.resize(len);
while(len--){
tree[len]=*(a+len);
}
}
void update(int x,int d){
while(x<tree.size()){
tree[x]+=d;
x+=lowbit(x);
}
}
T sum(int x){
int ans=0;
while(x>0){
ans+=tree[x];
x-=lowbit(x);
}
return ans;
}
T sum(int l,int r){
return sum(r)-sum(l-1);
}
};
线段树
struct{
int l,r,sum=0,lazy=0;
}st[200005];
int get(int l,int r){
return (l+r-2)|(l!=r);
}
void build(int l,int r){
st[get(l,r)].l=l;
st[get(l,r)].r=r;
if(l!=r){
build(l,l+r>>1);
build((l+r>>1)+1,r);
st[get(l,r)].sum=st[get(l,l+r>>1)].sum+st[get((l+r>>1)+1,r)].sum;
}else{
st[get(l,r)].sum=a[l];
}
}
void pushdown(int l,int r){
st[get(l,l+r>>1)].sum+=st[get(l,r)].lazy*((l+r>>1)-l+1);
st[get((l+r>>1)+1,r)].sum+=st[get(l,r)].lazy*(r-(l+r>>1));
st[get(l,l+r>>1)].lazy+=st[get(l,r)].lazy;
st[get((l+r>>1)+1,r)].lazy+=st[get(l,r)].lazy;
st[get(l,r)].lazy=0;
}
void update(int l,int r,const int left,const int right,const int k){
if(l>=left&&r<=right){
st[get(l,r)].sum+=k*(r-l+1);
st[get(l,r)].lazy+=k;
}else{
if(st[get(l,r)].lazy&&l!=r){
pushdown(l,r);
}
if(left<=l+r>>1){
update(l,l+r>>1,left,right,k);
}
if(right>l+r>>1){
update((l+r>>1)+1,r,left,right,k);
}
st[get(l,r)].sum=st[get(l,l+r>>1)].sum+st[get((l+r>>1)+1,r)].sum;
}
}
int query(int l,int r,const int left,const int right){
if(l>=left&&r<=right){
return st[get(l,r)].sum;
}else{
if(st[get(l,r)].lazy&&l!=r){
pushdown(l,r);
}
int ans=0;
if(left<=l+r>>1){
ans+=query(l,l+r>>1,left,right);
}
if(right>l+r>>1){
ans+=query((l+r>>1)+1,r,left,right);
}
return ans;
}
}
二叉搜索树
template <typename T>
struct Node{
T data;
Node *left;
Node *right;
};
template <typename T>
class binarySearchTreeC{
private:
Node<T> *root;
Node<T> *insertNode(Node<T> *node,T data){
if(node==nullptr){
node=new Node<T>;
node->data=data;
node->left=nullptr;
node->right=nullptr;
}else if(data<node->data){
node->left=insertNode(node->left,data);
}else if(data>node->data){
node->right=insertNode(node->right,data);
}
return node;
}
Node<T> *findMinNode(Node<T> *node){
while(node->left!=nullptr){
node=node->left;
}
return node;
}
Node<T> *deleteNode(Node<T> *node,T data){
if(node==nullptr){
return node;
}else if(data<node->data){
node->left=deleteNode(node->left,data);
}else if(data>node->data){
node->right=deleteNode(node->right,data);
}else{
if(node->left==nullptr){
Node<T> *temp=node->right;
delete node;
return temp;
}else if(node->right==nullptr){
Node<T> *temp=node->left;
delete node;
return temp;
}
Node<T> *temp=findMinNode(node->right);
node->data=temp->data;
node->right=deleteNode(node->right,temp->data);
}
return node;
}
Node<T> *searchNode(Node<T> *node,T data){
if(node==nullptr||node->data==data){
return node;
}
if(node->data<data){
return searchNode(node->right,data);
}
return searchNode(node->left,data);
}
void preOrderTraversal(Node<T> *node){
if(node!=nullptr){
cout<<node->data<<" ";
preOrderTraversal(node->left);
preOrderTraversal(node->right);
}
}
void inOrderTraversal(Node<T> *node){
if(node!=nullptr){
InOrderTraversal(node->left);
cout<<node->data<<" ";
InOrderTraversal(node->right);
}
}
void postOrderTraversal(Node<T> *node){
if(node!=nullptr){
PostOrderTraversal(node->left);
PostOrderTraversal(node->right);
cout<<node->data<<" ";
}
}
public:
void BinarySearchTree(){ //建树
root=nullptr;
}
void insert(int data){ //插入
root=insertNode(root,data);
}
void remove(int data){ //删除
root=deleteNode(root,data);
}
void preorder(){ //先序遍历
preOrderTraversal(root);
}
void inorder(){ //中序遍历
inOrderTraversal(root);
}
void postorder(){ //后序遍历
postOrderTraversal(root);
}
Node<T> *search(T data){ //查找
return searchNode(root,data);
}
};
AVL
class AVLTree{
private:
struct Node{
int key,left,right,height;
Node():key(0),left(-1),right(-1),height(1){}
};
Node nodes[100];
int root,nodeCount;
int height(int nodeIndex){
if(nodeIndex==-1){
return 0;
}
return nodes[nodeIndex].height;
}
int balanceFactor(int nodeIndex){
if(nodeIndex==-1){
return 0;
}
return height(nodes[nodeIndex].left) - height(nodes[nodeIndex].right);
}
void updateHeight(int nodeIndex){
if(nodeIndex==-1){
return;
}
nodes[nodeIndex].height=1 + max(height(nodes[nodeIndex].left), height(nodes[nodeIndex].right));
}
int rotateRight(int y){
int x=nodes[y].left;
int T2=nodes[x].right;
nodes[x].right=y;
nodes[y].left=T2;
updateHeight(y);
updateHeight(x);
return x;
}
int rotateLeft(int x){
int y=nodes[x].right;
int T2=nodes[y].left;
nodes[y].left=x;
nodes[x].right=T2;
updateHeight(x);
updateHeight(y);
return y;
}
int balance(int nodeIndex){
int balance=balanceFactor(nodeIndex);
if (balance>1){
if (balanceFactor(nodes[nodeIndex].left)<0){
nodes[nodeIndex].left=rotateLeft(nodes[nodeIndex].left);
}
return rotateRight(nodeIndex);
}
if (balance<-1){
if (balanceFactor(nodes[nodeIndex].right)>0){
nodes[nodeIndex].right=rotateRight(nodes[nodeIndex].right);
}
return rotateLeft(nodeIndex);
}
return nodeIndex;
}
int findMin(int nodeIndex){
while (nodes[nodeIndex].left!=-1){
nodeIndex=nodes[nodeIndex].left;
}
return nodeIndex;
}
int deleteNode(int nodeIndex, int key){
if (nodeIndex==-1) return nodeIndex;
if (key<nodes[nodeIndex].key){
nodes[nodeIndex].left=deleteNode(nodes[nodeIndex].left, key);
}else if (key>nodes[nodeIndex].key){
nodes[nodeIndex].right=deleteNode(nodes[nodeIndex].right, key);
}else{
if (nodes[nodeIndex].left==-1){
int temp=nodes[nodeIndex].right;
nodes[nodeIndex]=nodes[temp];
return temp;
}else if (nodes[nodeIndex].right==-1){
int temp=nodes[nodeIndex].left;
nodes[nodeIndex]=nodes[temp];
return temp;
}else{
int temp=findMin(nodes[nodeIndex].right);
nodes[nodeIndex].key=nodes[temp].key;
nodes[nodeIndex].right=deleteNode(nodes[nodeIndex].right, nodes[temp].key);
}
}
updateHeight(nodeIndex);
return balance(nodeIndex);
}
public:
AVLTree():root(-1),nodeCount(0){}
void insert(int key){
root=insert(root,key);
}
int insert(int nodeIndex,int key){
if(nodeIndex==-1){
if(nodeCount>=100){
return -1;
}
nodes[nodeCount].key=key;
nodes[nodeCount].left=-1;
nodes[nodeCount].right=-1;
nodeCount++;
return nodeCount-1;
}
if(key<nodes[nodeIndex].key){
nodes[nodeIndex].left=insert(nodes[nodeIndex].left,key);
}else if(key>nodes[nodeIndex].key){
nodes[nodeIndex].right=insert(nodes[nodeIndex].right,key);
}else{
return nodeIndex;
}
updateHeight(nodeIndex);
return balance(nodeIndex);
}
void deleteKey(int key){
root=deleteNode(root,key);
}
void preOrder(int nodeIndex){
if(nodeIndex==-1){
return;
}
preOrder(nodes[nodeIndex].left);
cout<<nodes[nodeIndex].key<<' ';
preOrder(nodes[nodeIndex].right);
}
void preOrder(){
preOrder(root);
}
};
红黑树
enum Color{
RED,BLACK
};
class RedBlackTree{
private:
struct Node{
int key,left,right,parent;
Color color;
Node():key(0),left(-1),right(-1),parent(-1),color(BLACK){}
};
Node nodes[100];
int root,size;
void leftRotate(int x){
int y=nodes[x].right;
nodes[x].right=nodes[y].left;
if(nodes[y].left!=-1){
nodes[nodes[y].left].parent=x;
}
nodes[y].parent=nodes[x].parent;
if(nodes[x].parent==-1){
root=y;
}else if(x==nodes[nodes[x].parent].left){
nodes[nodes[x].parent].left=y;
}else{
nodes[nodes[x].parent].right=y;
}
nodes[y].left=x;
nodes[x].parent=y;
}
void rightRotate(int x){
int y=nodes[x].left;
nodes[x].left=nodes[y].right;
if(nodes[y].right!=-1){
nodes[nodes[y].right].parent=x;
}
nodes[y].parent=nodes[x].parent;
if(nodes[x].parent==-1){
root=y;
}else if(x==nodes[nodes[x].parent].right){
nodes[nodes[x].parent].right=y;
}else{
nodes[nodes[x].parent].left=y;
}
nodes[y].right=x;
nodes[x].parent=y;
}
void fixInsert(int k){
int u;
while(nodes[nodes[k].parent].color==RED){
if(nodes[k].parent==nodes[nodes[nodes[k].parent].parent].right){
u=nodes[nodes[nodes[k].parent].parent].left;
if(nodes[u].color==RED){
nodes[u].color=BLACK;
nodes[nodes[k].parent].color=BLACK;
nodes[nodes[nodes[k].parent].parent].color=RED;
k=nodes[nodes[k].parent].parent;
}else{
if(k==nodes[nodes[k].parent].left){
k=nodes[k].parent;
rightRotate(k);
}
nodes[nodes[k].parent].color=BLACK;
nodes[nodes[nodes[k].parent].parent].color=RED;
leftRotate(nodes[nodes[k].parent].parent);
}
}else{
u=nodes[nodes[nodes[k].parent].parent].right;
if(nodes[u].color==RED){
nodes[u].color=BLACK;
nodes[nodes[k].parent].color=BLACK;
nodes[nodes[nodes[k].parent].parent].color=RED;
k=nodes[nodes[k].parent].parent;
}else{
if(k==nodes[nodes[k].parent].right){
k=nodes[k].parent;
leftRotate(k);
}
nodes[nodes[k].parent].color=BLACK;
nodes[nodes[nodes[k].parent].parent].color=RED;
rightRotate(nodes[nodes[k].parent].parent);
}
}
if(k==root){
break;
}
}
nodes[root].color=BLACK;
}
void fixDelete(int x){
int s;
while(x!=root && nodes[x].color==BLACK){
if(x==nodes[nodes[x].parent].left){
s=nodes[nodes[x].parent].right;
if(nodes[s].color==RED){
nodes[s].color=BLACK;
nodes[nodes[x].parent].color=RED;
leftRotate(nodes[x].parent);
s=nodes[nodes[x].parent].right;
}
if(nodes[nodes[s].left].color==BLACK && nodes[nodes[s].right].color==BLACK){
nodes[s].color=RED;
x=nodes[x].parent;
}else{
if(nodes[nodes[s].right].color==BLACK){
nodes[nodes[s].left].color=BLACK;
nodes[s].color=RED;
rightRotate(s);
s=nodes[nodes[x].parent].right;
}
nodes[s].color=nodes[nodes[x].parent].color;
nodes[nodes[x].parent].color=BLACK;
nodes[nodes[s].right].color=BLACK;
leftRotate(nodes[x].parent);
x=root;
}
}else{
s=nodes[nodes[x].parent].left;
if(nodes[s].color==RED){
nodes[s].color=BLACK;
nodes[nodes[x].parent].color=RED;
rightRotate(nodes[x].parent);
s=nodes[nodes[x].parent].left;
}
if(nodes[nodes[s].right].color==BLACK && nodes[nodes[s].left].color==BLACK){
nodes[s].color=RED;
x=nodes[x].parent;
}else{
if(nodes[nodes[s].left].color==BLACK){
nodes[nodes[s].right].color=BLACK;
nodes[s].color=RED;
leftRotate(s);
s=nodes[nodes[x].parent].left;
}
nodes[s].color=nodes[nodes[x].parent].color;
nodes[nodes[x].parent].color=BLACK;
nodes[nodes[s].left].color=BLACK;
rightRotate(nodes[x].parent);
x=root;
}
}
}
nodes[x].color=BLACK;
}
void transplant(int u, int v){
if(nodes[u].parent==-1){
root=v;
}else if(u==nodes[nodes[u].parent].left){
nodes[nodes[u].parent].left=v;
}else{
nodes[nodes[u].parent].right=v;
}
nodes[v].parent=nodes[u].parent;
}
int minimum(int node){
while(nodes[node].left!=-1){
node=nodes[node].left;
}
return node;
}
public:
RedBlackTree(){
size=0;
root=-1;
}
void insert(int key){
if(size >= 100){
cout << "Tree is full" << endl;
return;
}
int node=size++;
nodes[node].key=key;
nodes[node].parent=-1;
nodes[node].left=-1;
nodes[node].right=-1;
nodes[node].color=RED;
int y=-1;
int x=root;
while(x!=-1){
y=x;
if(key<nodes[x].key){
x=nodes[x].left;
}else{
x=nodes[x].right;
}
}
nodes[node].parent=y;
if(y==-1){
root=node;
}else if(key<nodes[y].key){
nodes[y].left=node;
}else{
nodes[y].right=node;
}
if(nodes[node].parent==-1){
nodes[node].color=BLACK;
return;
}
if(nodes[nodes[node].parent].parent==-1){
return;
}
fixInsert(node);
}
void deleteNode(int key){
int node=root;
while(node!=-1 && nodes[node].key!=key){
if(key<nodes[node].key){
node=nodes[node].left;
}else{
node=nodes[node].right;
}
}
if(node==-1){
return;
}
int y=node;
int yOriginalColor=nodes[y].color;
int x;
if(nodes[y].left==-1){
x=nodes[y].right;
transplant(y, nodes[y].right);
}else if(nodes[y].right==-1){
x=nodes[y].left;
transplant(y, nodes[y].left);
}else{
y=minimum(nodes[y].right);
yOriginalColor=nodes[y].color;
x=nodes[y].right;
if(nodes[y].parent==node){
nodes[x].parent=y;
}else{
transplant(y, nodes[y].right);
nodes[y].right=nodes[node].right;
nodes[nodes[y].right].parent=y;
}
transplant(node, y);
nodes[y].left=nodes[node].left;
nodes[nodes[y].left].parent=y;
nodes[y].color=nodes[node].color;
}
if(yOriginalColor==BLACK){
fixDelete(x);
}
}
void inOrderHelper(int node){
if(node!=-1){
inOrderHelper(nodes[node].left);
cout<<nodes[node].key<<" ";
inOrderHelper(nodes[node].right);
}
}
void inOrder(){
inOrderHelper(root);
}
};
FHQ Treap
struct node{
int key,val,l,r,sz;
i64 sum;
}tr[1000005];
int root,cnt;
int newnode(int v){
++cnt;
tr[cnt].key=rand();
tr[cnt].val=v;
tr[cnt].l=tr[cnt].r=0;
tr[cnt].sz=1;
tr[cnt].sum=v;
return cnt;
}
void pushup(int x){
if(!x){
return;
}
int l=tr[x].l,r=tr[x].r;
tr[x].sz=tr[l].sz+tr[r].sz+1;
tr[x].sum=tr[l].sum+tr[r].sum+tr[x].val;
}
void pushdown(int x){
if(!x){
return;
}
}
_Pi splitbyval(int x,int v){
if(!x){
return{0,0};
}
pushdown(x);
if(tr[x].val<=v){
auto p=splitbyval(tr[x].r,v);
tr[x].r=p.first;
pushup(x);
return{x,p.second};
}else{
auto p=splitbyval(tr[x].l,v);
tr[x].l=p.second;
pushup(x);
return{p.first,x};
}
}
_Pi splitbysize(int x,int k){
if(!x){
return{0,0};
}
pushdown(x);
int lsz=tr[tr[x].l].sz;
if(lsz+1<=k){
auto p=splitbysize(tr[x].r,k-lsz-1);
tr[x].r=p.first;
pushup(x);
return{x,p.second};
}else{
auto p=splitbysize(tr[x].l,k);
tr[x].l=p.second;
pushup(x);
return{p.first,x};
}
}
int merge(int x,int y){
if(!x||!y){
return x+y;
}
pushdown(x);
pushdown(y);
if(tr[x].key>tr[y].key){
tr[x].r=merge(tr[x].r,y);
pushup(x);
return x;
}else{
tr[y].l=merge(x,tr[y].l);
pushup(y);
return y;
}
}
void insert(int v){
auto p=splitbyval(root,v);
root=merge(merge(p.first,newnode(v)),p.second);
}
void del(int v){
auto p1=splitbyval(root,v-1);
auto p2=splitbyval(p1.second,v);
if(p2.first){
p2.first=merge(tr[p2.first].l,tr[p2.first].r);
}
root=merge(p1.first,merge(p2.first,p2.second));
}
int getrank(int v){
auto p=splitbyval(root,v-1);
int res=tr[p.first].sz+1;
root=merge(p.first,p.second);
return res;
}
int getkth(int k){
auto p1=splitbysize(root,k-1);
auto p2=splitbysize(p1.second,1);
int res=tr[p2.first].val;
root=merge(p1.first,merge(p2.first,p2.second));
return res;
}
int getpre(int v){
auto p=splitbyval(root,v-1);
auto p2=splitbysize(p.first,tr[p.first].sz-1);
int res=tr[p2.second].val;
root=merge(merge(p2.first,p2.second),p.second);
return res;
}
int getnxt(int v){
auto p=splitbyval(root,v);
auto p2=splitbysize(p.second,1);
int res=tr[p2.first].val;
root=merge(p.first,merge(p2.first,p2.second));
return res;
}
倍增
LCA
vector<int>v[500005];
int fa[500005][25],cost[500005][25],dep[500005];
int n,m,a,b,s;
// dfs，用来为 lca 算法做准备。接受两个参数：dfs 起始节点和它的父亲节点。
void dfs(int root,int fno){
// 初始化：第 2^0=1 个祖先就是它的父亲节点，dep 也比父亲节点多 1。
fa[root][0]=fno;
dep[root]=dep[fno]+1;
// 初始化：其他的祖先节点：第 2^i 的祖先节点是第 2^(i-1) 的祖先节点的第
// 2^(i-1) 的祖先节点。
for(int i=1;i<=20;i++){
fa[root][i]=fa[fa[root][i-1]][i-1];
}
// 遍历子节点来进行 dfs。
int sz=v[root].size();
for(int i=0;i<sz;i++){
if(v[root][i]==fno){
continue;
}
dfs(v[root][i],root);
}
}
// lca。用倍增算法算取 x 和 y 的 lca 节点。
int lca(int x,int y){
// 令 y 比 x 深。
if(dep[x]>dep[y]){
swap(x,y);
}
// 令 y 和 x 在一个深度。
int tmp=dep[y]-dep[x];
for(int j=0;tmp;j++,tmp>>=1){
if(tmp&1){
y=fa[y][j];
}
}
// 如果这个时候 y=x，那么 x，y 就都是它们自己的祖先。
if(y==x){
return x;
}
// 不然的话，找到第一个不是它们祖先的两个点。
for(int j=20;j>=0&&y!=x;j--){
if(fa[x][j]!=fa[y][j]){
x=fa[x][j];
y=fa[y][j];
}
}
// 返回结果。
return fa[x][0];
}
ST表
int f[1005][20],a[1005],LOGN[1005],n,m,l,r;
void getlog(int k=2){
LOGN[0]=LOGN[1]=0;
for(int i=2;i<n+2;i++){
LOGN[i]=LOGN[i/k]+1;
}
}
void ST(int n){
for(int i=0;i<n;i++){
f[i][0]=a[i];
}
for(int j=1;(1<<j)<=n;j++){
for(int i=0;i+(1<<j)<=n;i++){
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
}
int RMQ(int l,int r){
return max(f[l][LOGN[r-l+1]],f[r-(1<<LOGN[r-l+1])+1][LOGN[r-l+1]]);
}
图论
存图
#### 直接存图
```cpp
struct edge{
int from,to,w;
edge(int _from=0,int _to=0,int _w=0){
from=_from;
to=_to;
w=_w;
}
}graph0[M];
int cnt0;
void init0(){
for(int i=0;i<n;i++){
graph0[i]=edge{0,0,0};
}
}
void addedge0(int from,int to,int w=1){
graph0[cnt0++]=edge{from,to,w};
}
int findedge0(int from,int to){
for(int i=0;i<cnt0;i++){
if(graph0[i].from==from&&graph0[i].to==to){
return graph0[i].w;
}
}
return -1;
}
```
复杂度：
- 查询是否存在某条边：$O(m)$。
- 遍历一个点的所有出边：$O(m)$。
- 遍历整张图：$O(nm)$。
- 空间复杂度：$O(m)$。
应用：由于直接存边的遍历效率低下，一般不用于遍历图。在 Kruskal 算法中，由于需要将边按边权排序，需要直接存边。在有的题目中，需要多次建图（如建一遍原图，建一遍反图），此时既可以使用多个其它数据结构来同时存储多张图，也可以将边直接存下来，
需要重新建图时利用直接存下的边来建图。
#### 邻接矩阵
```cpp
int graph1[1005][1005];
void init1(int a=-1){
memset(graph1,a,sizeof graph1);
}
void addedge1(int from,int to,int w=1){
graph1[from][to]=w;
}
int findedge1(int from,int to){
return graph1[from][to];
}
```
复杂度：
- 查询是否存在某条边：$O(1)$。
- 遍历一个点的所有出边：$O(n)$。
- 遍历整张图：$O(n^2)$。
- 空间复杂度：$O(n^2)$。
应用：邻接矩阵只适用于没有重边（或重边可以忽略）的情况。其最显著的优点是可以 $O(1)$ 查询一条边是否存在。由于邻接矩阵在稀疏图上效率很低（尤其是在点数较多的图上，空间无法承受），所以一般只会在稠密图上使用邻接矩阵。
#### 邻接表
```
vector<pair<int,int>>graph2[1005];
void init2(){
for(int i=0;i<n;i++){
graph2[i].clear();
}
}
void addedge2(int from,int to,int w=1){
graph2[from].emplace_back(to,w);
}
int findedge2(int from,int to){
for(int i=0;i<int(graph2[from].size());i++){
if(graph2[from][i].first==to){
return graph2[from][i].second;
}
}
return -1;
}
```
复杂度：
- 查询是否存在 $u$ 到 $v$ 的边：$O(d^+(u))$（如果事先进行了排序就可以使用 二分查找 做到 $O(\log(d^+(u))))$。
- 遍历点 u 的所有出边：O(d^+(u))。
- 遍历整张图：O(n+m)。
- 空间复杂度：O(m)。
应用：存各种图都很适合，除非有特殊需求（如需要快速查询一条边是否存在，尤其适用于需要对一个点的所有出边进行排序的场合。
#### 链式前向星
```cpp
int head[1005],from[M],nxt[M],to[M],w[M],cnt; //from可省略
void init(){
memset(head,-1,sizeof head);
memset(from,-1,sizeof from);
memset(nxt,-1,sizeof nxt);
memset(to,-1,sizeof to);
cnt=0;
}
void addedge(int f,int t,int ww){
nxt[++cnt]=head[f];
head[f]=cnt;
to[cnt]=t;
w[cnt]=ww;
from[cnt]=f;
}
int findedge(int f,int t){
for(int i=f;~i;i=nxt[i]){
if(to[i]==t){
return w[i];
}
}
return -1;
}
```
复杂度：
- 查询是否存在 $u$ 到 $v$ 的边：$O(d^+(u))$。
- 遍历点 $u$ 的所有出边：$O(d^+(u))$。
- 遍历整张图：$O(n+m)$。
- 空间复杂度：$O(m)$。
应用：存各种图都很适合，但不能快速查询一条边是否存在，也不能方便地对一个点的出边进行排序。优点是边是带编号的，有时会非常有用，而且如果 `cnt` 的初始值为奇数，存双向边时 `i ^ 1` 即是 `i` 的反边（常用于 网络流）。
### 拓扑排序
```cpp
vector<int>topo;
bool toposort(){
for(int i=0;i<n;i++){
for(auto j:graph[i]){
in[j.first]++;
}
}
int u;
queue<int>q;
for(int i=0;i<n;i++){
if(in[i]==0){
q.push(i);
}
}
while(!q.empty()){
u=q.front();
q.pop();
topo.push_back(u);
for(auto i:graph[u]){
in[i.first]--;
if(in[i.first]==0){
q.push(i.first);
}
}
}
if(int(topo.size())==n){
return 1;
}
return 0;
}
```
### Bellman-Ford
```cpp
int dis[1005],from,v,w;
bool Bellman_Ford(int s){
memset(dis,0x3f,sizeof dis);
dis[s]=0;
bool flag; //判负环(从s能达到的)
for(int i=0;i<n;i++){
flag=0;
for(int j=0;j<cnt;j++){
if(dis[from]==0x3f3f3f3f){
continue;
}
//无穷大与常数加减仍然为无穷大
//因此最短路长度为0x3f3f3f3f的点引出的边不可能发生松弛操作
if(dis[edge[j].to]>dis[edge[j].from]+edge[j].w){
dis[edge[j].to]=dis[edge[j].from]+edge[j].w;
flag=1;
}
}
//没有可以松弛的边时就停止算法
if(!flag){
break;
}
}
//第n轮循环仍然可以松弛时说明s点可以抵达一个负环
return flag;
}
```
### SPFA
```cpp
int dis[1005],cnt[1005],vis[1005];
queue<int>q;
bool SPFA(int s){ //返回是否存在负环
memset(dis,0x3f,sizeof dis);
memset(cnt,0,sizeof cnt);
memset(vis,0,sizeof vis);
dis[s]=0;
vis[s]=1;
q.push(s);
while(!q.empty()){
vis[q.front()]=0;
for(auto i:edge[q.front()]){
if(dis[i.first]>dis[q.front()]+i.second){
dis[i.first]=dis[q.front()]+i.second;
cnt[i.first]=cnt[q.front()]+1;//记录最短路经过的边数
if(cnt[i.first]>=n){
return 1;
}
//在不经过负环的情况下，最短路至多经过n-1条边
//因此如果经过了多于n条边，一定说明经过了负环
if(!vis[i.first]){
q.push(i.first);
vis[i.first]=1;
}
}
}
q.pop();
}
return 0;
}
```
### Dijkstra（暴力）
```cpp
void notUseHeapDijkstra(int s){
memset(dis,0x3f,sizeof dis);
memset(vis,0,sizeof vis);
dis[s]=0;
int u,mind,v,w;
for(int i=0;i<n;i++){
u=0;
mind=0x3f3f3f3f;
for(int j=1;j<=n;j++){
if(!vis[j]&&dis[j]<mind){
u=j;
mind=dis[j];
}
}
vis[u]=1;
for(auto i:e[u]){
if(dis[i.first]>dis[u]+i.second){
dis[i.first]=dis[u]+i.second;
}
}
}
}
```
### Dijkstra（堆）
```cpp
struct node{
int dis,u;
bool operator<(const node &a)const{
return this->dis>a.dis;
}
};
priority_queue<node>q;
void useHeapDijkstra(int s){
memset(dis,0x3f,sizeof dis);
memset(vis,0,sizeof vis);
int u,v,w;
dis[s]=0;
q.push({0,s});
while(q.size()){
u=q.top().u;
q.pop();
if(vis[u]){
continue;
}
vis[u]=1;
for(auto i:e[u]){
if(dis[v]>dis[u]+w){
if(dis[i.first]>dis[u]+i.second){
dis[i.first]=dis[u]+i.second;
q.push({dis[i.first],i.first});
}
}
}
}
}
```
### Floyd_Warshall
```cpp
int f[1005][1005];
bool Floyd(){ //返回有没有负环
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
}
}
//判负环
for(int i=0;i<n;i++){
if(f[i][i]<0){
return 1;
}
}
return 0;
}
```
### Kruskal
```cpp
int findroot(int x){
return fa[x]==x?x:fa[x]=findroot(fa[x]);
}
void merge(int x,int y){
x=findroot(x);
y=findroot(y);
fa[x]=y;
}
bool cmp(Edge A,Edge B){
return A.w<B.w;
}
int Kruskal(){
sort(edge,edge+cntedge,cmp);
int tot=0,ans=0,xr,yr;
for(int i=0;i<cntedge;i++){
xr=findroot(edge[i].u);
yr=findroot(edge[i].v);
if(xr!=yr){
Merge(xr,yr);
tot++;
ans+=edge[i].w;
}
if(tot>=b){
return ans;
}
}
return -1;//图不连通
}
```
### Prim（暴力）
```cpp
void notUseHeapPrim(int s){
memset(dis,0x3f,sizeof dis);
memset(vis,0,sizeof vis);
dis[s]=0;
int u,mind,v,w;
for(int i=0;i<n;i++){
u=0;
mind=0x3f3f3f3f;
for(int j=1;j<=n;j++){
if(!vis[j]&&dis[j]<mind){
u=j;
mind=dis[j];
}
}
vis[u]=1;
for(auto i:e[u]){
if(dis[i.first]>i.second){
dis[i.first]=i.second;
}
}
}
}
```
### Prim（堆）
```cpp
struct cmp{
bool operator () (_Pi a,_Pi b){
return a.first>b.first;
}
};
_SPQ(_Pi,cmp) q;
bool useHeapPrim(){
int cnt=0;
_Pi t;
assmax_s(d);
d[1]=0;
q.push({0,1});
while(q.size()){
if(cnt==n){
break;
}
t=q.top();
q.pop();
if(inmst[t.second]){
continue;
}
inmst[t.second]=1;
cnt++;
sum+=t.first;
for(auto i:e[t.second]){
if(!inmst[i.first]&&i.second<d[i.first]){
d[i.first]=i.second;
q.push({i.second,i.first});
}
}
}
return cnt!=n;
}
```
### 匈牙利算法
```cpp
bool find(int x){
for(auto i:e[x]){
if(vis[i]){
continue;
}
vis[i]=1;
if(a[i]==-1||find(a[i])){
a[i]=x;
return 1;
}
}
return 0;
}
int hungary(){
int ans=0;
assneg(a);
for(int i=1;i<=n;i++){
clr(vis);
if(find(i)){
ans++;
}
}
return ans;
}
```
### Edmonds–Karp
```cpp
void add_edge(int u,int v,int w){
e[cnt]={v,head[u],w};
head[u]=cnt++;
e[cnt]={u,head[v],0};
head[v]=cnt++;
} //奇偶存图
int Edmonds_Karp(int s,int t){
int mflow=0;
while(1){
clr(flow);
flow[s]=0x3f3f3f3f3f3f3f3f;
q.push(s);
while(q.size()){
for(int i=head[q.front()];~i;i=e[i].next){
v=e[i].to;
if(!flow[v]&&e[i].cap>0){
pre[v]=i;
flow[v]=min(flow[q.front()],(int)e[i].cap);
q.push(v);
}
}
q.pop();
}
if(!flow[t]){
break;
}
for(int i=t;i!=s;i=e[pre[i]^1].to){
e[pre[i]].cap-=flow[t];
e[pre[i]^1].cap+=flow[t];
}
mflow+=flow[t];
}
return mflow;
}
```
### Dinic
```cpp
void add_edge(int u,int v,int w){
e[idx]={v,head[u],w};
head[u]=idx++;
e[idx]={u,head[v],0};
head[v]=idx++;
}
bool bfs(int s,int t){
assneg(level);
queue<int>q;
level[s]=0;
q.push(s);
while(q.size()){
for(int i=head[q.front()];~i;i=e[i].next){
v=e[i].to;
if(level[v]<0&&e[i].cap>0){
level[v]=level[q.front()]+1;
q.push(v);
if(v==t){
return 1;
}
}
}
q.pop();
}
return 0;
}
int dfs(int u,int t,int min_flow){
if(u==t){
return min_flow;
}
for(int &i=cur[u];~i;i=e[i].next){
v=e[i].to;
if(level[v]==level[u]+1&&e[i].cap>0){
w=dfs(v,t,min(min_flow,e[i].cap));
if(w>0){
e[i].cap-=w;
e[i^1].cap+=w;
return w;
}
}
}
return 0;
}
int dinic(int s,int t){
int max_flow=0;
while(bfs(s,t)){
memcpy(cur,head,sizeof cur);
while((w=dfs(s,t,INF))>0){
max_flow+=w;
}
}
return max_flow;
}
```
### ISAP
```cpp
struct Edge{
int to,next,cap;
}e[20005];
int head[205],cnt,pre[205],gap[205],d[205],cur[205];
int n,m,s,t,u,v,w;
void add_edge(int u,int v,int w){
e[cnt]={v,head[u],w};
head[u]=cnt++;
e[cnt]={u,head[v],0};
head[v]=cnt++;
}
void bfs(){
assneg(d);
clr(gap);
queue<int> q;
q.push(t);
d[t]=0;
gap[0]=1;
while(q.size()){
for(int i=head[q.front()];~i;i=e[i].next){
int v=e[i].to;
if(d[v]==-1){
d[v]=d[q.front()]+1;
gap[d[v]]++;
q.push(v);
}
}
q.pop();
}
}
int ISAP(int s,int t){
bfs();
memcpy(cur,head,sizeof(head));
u=s;
int flow=0,i,f,neck;
while(d[s]<n){
if(u==t){
f=0x3f3f3f3f3f3f3f3f;
for(int i=s;i!=t;i=e[cur[i]].to){
if(f>e[cur[i]].cap){
f=e[cur[i]].cap;
neck=i;
}
}
for(int i=s;i!=t;i=e[cur[i]].to){
e[cur[i]].cap-=f;
e[cur[i]^1].cap+=f;
}
flow+=f;
u=neck;
}
for(i=cur[u];~i;i=e[i].next){
if(e[i].cap>0&&d[u]==d[e[i].to]+1){
break;
}
}
if(~i){
cur[u]=i;
pre[e[i].to]=u;
u=e[i].to;
}else{
if(--gap[d[u]]==0){
break;
}
int mind=n;
for(int i=head[u];~i;i=e[i].next){
if(e[i].cap>0&&mind>d[e[i].to]){
mind=d[e[i].to];
cur[u]=i;
}
}
d[u]=mind+1;
gap[d[u]]++;
if(u!=s){
u=pre[u];
}
}
}
return flow;
}
```
### tarjan
#### 强连通分量
```cpp
void tarjan(int u){
low[u]=dfn[u]=++dfnc;
st.push(u);
inst[u]=1;
_FE(i,e[u]){
if(!dfn[i]){
tarjan(i);
low[u]=min(low[u],low[i]);
}else if(inst[u]){
low[u]=min(low[u],dfn[i]);
}
}
if(dfn[u]==low[u]){
sccc++;
while(st.top()!=u){
scc[st.top()]=sccc;
sz[sccc]++;
inst[st.top()]]=0;
st.pop();
}
}
}
```
#### 割点（割顶）
```cpp
void tarjan(int u,int fa){
low[u]=dfn[u]=++cnt;
int ch=0;
_FE(i,e[u]){
if(!dfn[i]){
ch++;
tarjan(i,u);
low[u]=min(low[u],low[i]);
if(fa!=u&&low[i]>=dfn[u]&&!f[u]){
f[u]=1;
ans++;
}
}else if(i!=fa){
low[u]=min(low[u],dfn[i]);
}
}
if(fa==u&&ch>=2&&!f[u]){
f[u]=1;
ans++;
}
}
```
#### 割边（桥）
```cpp
void tarjan(int u,int fa){
bool fl=0;
fat[u]=fa;
low[u]=dfn[u]=++cnt;
_FE(i,e[u]){
if(!dfn[i]){
tarjan(i,u);
low[u]=min(low[u],low[i]);
if(low[i]>dfn[u]){
f[i]=1;
ans++;
}
}else{
if(i!=fa||fl){
low[u]=min(low[u],dfn[i]);
}else{
fl=1;
}
}
}
}
```
#### 点双连通分量
```cpp
void tarjan(int u,int las){
low[u]=dfn[u]=++cnt;
st.push(u);
_FE(i,e[u]){
if(i.second==(las^1)){
continue;
}
if(!dfn[i.first]){
tarjan(i.first,i.second);
low[u]=min(low[u],low[i.first]);
}else{
low[u]=min(low[u],dfn[i.first]);
}
}
if(dfn[u]==low[u]){
ans.emplace_back(1,u);
while(st.top()!=u){
ans.back().push_back(st.top());
st.pop();
}
st.pop();
}
}
```
### 树的直径
```cpp
void dfs(int u,int fa){
s[u]=1;
f[u]=0;
_FE(i,e[u]){
if(i!=fa){
dfs(i,u);
s[u]+=s[i];
f[u]=max(f[u],s[i]);
}
}
f[u]=max(f[u],n-s[u]);
}
//f数组最小值的下标是树的重心
```
## 数论
### Miller-Rabin
```cpp
constexpr int p[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
ll mul(ll x,ll y,ll m){
return __int128(x)*y%m;
}
int fastpow(ll a,ll b,ll m){
if(!a){
return 0;
}
if(a==1||!b){
return 1;
}
a%=m;
ll ans=1;
while(b){
if(b&1){
ans=mul(ans,a,m);
}
a=mul(a,a,m);
b>>=1;
}
return ans;
}
bool miller_rabin(ll x){
if(x<=2){
return x==2;
}
if(!(x&1)){
return 0;
}
ll s=x-1,t=__builtin_ctzll(s),r;
s>>=t;
for(int i=0;i<25&&p[i]<x;i++){
if(!(x%p[i])){
return 0;
}
r=fastpow(p[i],s,x);
if(r==1||r==x-1||r==0){
continue;
}
for(int j=1;j<=t;j++){
r=mul(r,r,x);
if(r==x-1&&j!=t){
r=1;
break;
}
if(r==1){
return 0;
}
}
if(r!=1){
return 0;
}
}
return 1;
}
```
### exgcd
#### 正常版
```cpp
ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b){
x=1;
y=0;
return a;
}
ll gcd=exgcd(b,a%b,y,x);
y-=a/b*x;
return gcd;
}
```
#### 逆天码风迭代版
```cpp
int exgcd(int a,int b,int &x,int &y){
int x0=1,x1=0,x2=0,x3=1,c;
while(b){
c=a/b;
tie(x0,x1,x2,x3,a,b)=make_tuple(x2,x3,x0-x2*c,x1-x3*c,b,a-b*c);
}
x=x0;
y=x1;
return a;
}
```
#### 求逆元
```cpp
int inv(int a,int m){
int x,y,g=exgcd(a,m,x,y);
if(~g){
return (x%m+m)%m;
}else{
return -1;
}
}
```
### CRT
```cpp
ll crt(){
for(int i=0;i<n;i++){
m*=b[i];
}
for(int i=0;i<n;i++){
res=m/b[i];
exgcd(res,b[i],t,y);
t%=b[i];
ans=(ans+a[i]*res*t)%m;
}
return (ans+m)%m;
}
```
### exCRT
```cpp
ll mul(ll a,ll b,ll mod){
return __int128(a)*b%mod;
}
ll excrt(){
ans=a[0];
m=b[0];
for(int i=1;i<n;i++){
res=((a[i]-ans)%b[i]+b[i])%b[i];
gcd=exgcd(m,b[i],t,y);
t=mul(t,res/gcd,b[i]);
ans+=t*m;
m=b[i]/gcd*m;
ans=(ans%m+m)%m;
}
return ans;
}
```
### FFT
#### 无优化
```cpp
void dft(complex<double> *a,int len,int type){
if(len==1){
return;
}
complex<double> *f0=a,*f1=a+len/2;
for(int i=0;i<len;i++){
sav[i]=a[i];
}
for(int i=0;i<(len>>1);i++){
f0[i]=sav[i<<1];
f1[i]=sav[i<<1|1];
}
dft(f0,len>>1,type);
dft(f1,len>>1,type);
complex<double> tg(cos(2*pi/len),type*sin(2*pi/len)),buf(1.L,0.L);
for(int i=0;i<(len>>1);i++){
sav[i]=f0[i]+buf*f1[i];
sav[i+(len>>1)]=f0[i]-buf*f1[i];
buf*=tg;
}
for(int i=0;i<len;i++){
a[i]=sav[i];
}
}
void work(){
for(;lim<=n+m;lim<<=1);
dft(f,lim,1);
dft(g,lim,1);
for(int i=0;i<=lim;i++){
f[i]*=g[i];
}
dft(f,lim,-1);
for(int i=0;i<=lim;i++){
ans[i]+=int(f[i].real()/lim+.5);
}
}
```
#### 迭代
```cpp
void fft(complex<double>* f,int len,int type){
for(int i=0;i<len;i++){
if(i<r[i]){
swap(f[i],f[r[i]]);
}
}
complex<double> wn,w,x,y;
for(int i=1;i<len;i<<=1){
wn={cos(pi/i),type*sin(pi/i)};
for(int l=i<<1,j=0;j<len;j+=l){
w={1,0};
for(int k=0;k<i;k++,w*=wn){
x=f[j+k];
y=w*f[j+i+k];
f[j+k]=x+y;
f[j+i+k]=x-y;
}
}
}
}
void work(){
for(;lim<=n+m;lim<<=1,l++);
for(int i=0;i<=lim;i++){
r[i]=r[i>>1]>>1|(i&1)<<l-1;
}
fft(f,lim,1);
fft(g,lim,1);
for(int i=0;i<=lim;i++){
f[i]*=g[i];
}
fft(f,lim,-1);
for(int i=0;i<=lim;i++){
ans[i]+=int(f[i].real()/lim+.5);
}
}
```
#### 三步变两步
```cpp
void fft(complex<double>* f,int len,int type){
for(int i=0;i<len;i++){
if(i<r[i]){
swap(f[i],f[r[i]]);
}
}
complex<double> wn,w,x,y;
for(int i=1;i<len;i<<=1){
wn={cos(pi/i),type*sin(pi/i)};
for(int l=i<<1,j=0;j<len;j+=l){
w={1,0};
for(int k=0;k<i;k++,w*=wn){
x=f[j+k];
y=w*f[j+i+k];
f[j+k]=x+y;
f[j+i+k]=x-y;
}
}
}
if(~type){
return;
}
for(int i=0;i<len;i++){
f[i]/=len;
}
}
void work(){
for(;lim<=n+m;lim<<=1,l++);
for(int i=0;i<=lim;i++){
r[i]=r[i>>1]>>1|(i&1)<<l-1;
}
fft(f,lim,1);
for(int i=0;i<=lim;i++){
f[i]*=f[i];
}
fft(f,lim,-1);
for(int i=0;i<=lim;i++){
ans[i]+=int(f[i].imag()/2+.5);
}
}
```
### NTT
```cpp
constexpr ll pri=332748118,pr=3,mod=998244353;
void ntt(ll* f,int len,int type){
for(int i=0;i<len;i++){
if(i<r[i]){
swap(f[i],f[r[i]]);
}
}
for(int i=1;i<len;i<<=1){
ll wn=fpow(type==1?pr:pri,(mod-1)/(i<<1),mod);
for(int l=i<<1,j=0;j<len;j+=l){
ll w=1;
for(int k=0;k<i;k++,w=w*wn%mod){
ll x=f[j+k],y=w*f[j+k+i]%mod;
f[j+k]=(x+y)%mod;
f[i+j+k]=(x-y+mod)%mod;
}
}
}
}
void work(){
for(;lim<=n+m;lim<<=1,l++);
for(int i=0;i<=lim;i++){
r[i]=r[i>>1]>>1|(i&1)<<l-1;
}
ntt(f,lim,1);
ntt(g,lim,1);
for(int i=0;i<=lim;i++){
f[i]*=g[i];
}
ntt(f,lim,-1);
inv=fpow(lim,mod-2,mod);
for(int i=0;i<=lim;i++){
ans[i]+=f[i]*inv%mod;
}
}
```
### 高斯消元
```cpp
void gauss(){
_FF(k,0,n){
maxi=l;
_FF(i,maxi+1,n){
if(abs(a[i][k])>abs(a[maxi][k])){
maxi=i;
}
}
if(abs(a[maxi][k])<1e-8){
continue;
}
_FF(i,0,n+1){
swap(a[l][i],a[maxi][i]);
}
_FF(i,0,n){
if(i==l){
continue;
}
res=a[i][k]/a[l][k];
_FF(j,k,n+1){
a[i][j]-=a[l][j]*res;
}
}
l++;
}
if(l<n){
cout<<"No Solution";
}else{
cout<<_SP(2);
_FF(i,0,n){
cout<<a[i][n]/a[i][i]<<'\n';
}
}
}
```
## 树剖
```cpp
void dfs1(int r){
son[r]=-1;
sz[r]=1;
for(auto i:e[r]){
if(!d[i]){
d[i]=d[r]+1;
fa[i]=r;
dfs1(i);
sz[r]+=sz[i];
if(son[r]==-1||sz[i]>sz[son[r]]){
son[r]=i;
}
}
}
}
void dfs2(int r,int t){
top[r]=t;
cnt++;
dfn[r]=cnt;
rnk[cnt]=r;
if(~son[r]){
dfs2(son[r],t);
for(auto i:e[r]){
if(i!=son[r]&&i!=fa[r]){
dfs2(i,i);
}
}
}
}
```
## 快读快写
```cpp
//类似于文件读入，要用Ctrl+Z或F6结束读入，再一起输出（方便调试）
//快读
namespace Fast_I{
char *_Buf,*_Start_ptr,*_End_ptr;
streambuf *inbuf;
unsigned int Size;
bool _Ok;
struct Fast_Istream{
operator bool(){
return _Ok;
}
Fast_Istream(streambuf *in,unsigned int Sz){
_Ok=1;
Fast_I::Size=Sz;
inbuf=in;
_Start_ptr=_End_ptr=_Buf=new char[Sz];
}
Fast_Istream(const char *in,unsigned int Sz){
_Ok=1;
Fast_I::Size=Sz;
rdbuf(in);
_Start_ptr=_End_ptr=_Buf=new char[Sz];
}
Fast_Istream(unsigned int Sz){
_Ok=1;
Fast_I::Size=Sz;
_Start_ptr=_End_ptr=_Buf=new char[Sz];
}
void rdbuf(const char *File){
static ifstream __In__(File);
rdbuf(__In__.rdbuf());
}
void Get_Char(char &_Val){
if(_Start_ptr==_End_ptr){
_Start_ptr=_Buf;
_End_ptr=_Buf+inbuf->sgetn(_Buf,Size);
}
if(_Start_ptr==_End_ptr){
_Val=-1;
_Ok=0;
}else{
_Val=*_Start_ptr++;
}
}
Fast_Istream &operator>>(char &_Val){
if(_Ok){
Get_Char(_Val);
while(_Val==32||_Val==10||_Val==13||_Val==8||_Val==9||_Val==7||_Val==12||_Val==11){
Get_Char(_Val);
}
}
return *this;
}
Fast_Istream &operator>>(char *_Val){
if(_Ok){
Get_Char(*_Val);
while(*_Val==32||*_Val==10||*_Val==13||*_Val==8||*_Val==9||*_Val==7||*_Val==12||*_Val==11){
Get_Char(*_Val);
}
while(*_Val!=32&&*_Val!=10&&*_Val&&*_Val!=-1&&*_Val!=9 &&*_Val!=11&&*_Val!=12&&~*_Val){
Get_Char(*++_Val);
}
*_Val=0;
--_Start_ptr;
}
return *this;
}
Fast_Istream &operator>>(string &_Val){
if(_Ok){
char c;
Get_Char(c);
while(c==32||c==10||c==13||c==8||c==9||c==7||c==12||c==11){
Get_Char(c);
}
for(_Val.clear();c!=32&&c!=10&&c&&c!=-1&&c!=9&&c!=11&&c!=12&&~c;Get_Char(c)){
_Val.push_back(c);
}
--_Start_ptr;
}
return *this;
}
template <typename Typex>
void Get_Int(Typex &_Val){
if(_Ok){
char ch;
bool _F=0;
for(Get_Char(ch);(ch<48||ch>57)&&~ch;Get_Char(ch)){
_F=ch==45;
}
for(_Val=0;ch>47&&ch<58&&~ch;Get_Char(ch)){
_Val=_Val*10+(ch^48);
}
if(_F){
_Val=~_Val+1;
}
--_Start_ptr;
}
}
template <typename Typex>
void Get_Unsigned(Typex &_Val){
if(_Ok){
char ch;
Get_Char(ch);
while((ch<48||ch>57)&&~ch){
Get_Char(ch);
}
for(_Val=0;ch>47&&ch<58&&~ch;Get_Char(ch)){
_Val=_Val*10+(ch^48);
}
--_Start_ptr;
}
}
template <typename Typex>
void Get_Double(Typex &_Val){
if(_Ok){
char ch;
bool _F=0;
for(Get_Char(ch);(ch<48||ch>57)&&~ch;Get_Char(ch)){
_F=ch==45;
}
for(_Val=0;ch>47&&ch<58&&~ch;Get_Char(ch)){
_Val=_Val*10+(ch^48);
}
if(ch==46){
unsigned long long _Pow=1;
for(Get_Char(ch);ch>47&&ch<58&&~ch;Get_Char(ch)){
_Val+=Typex((ch^48)*1.0/(_Pow*=10));
}
}
if(_F){
_Val=-_Val;
}
--_Start_ptr;
}
}
Fast_Istream &operator>>(bool &_Val){
if(_Ok){
char ch;
Get_Char(ch);
while(ch==32||ch==10||ch==13||ch==8||ch==9||ch==7||ch==12||ch==11){
Get_Char(ch);
}
while(ch!=32&&ch!=10&&ch&&~ch&&ch!=9&&ch!=11&&ch!=12&&~ch){
_Val|=ch!=48;
Get_Char(ch);
}
--_Start_ptr;
}
return *this;
}
Fast_Istream &operator>>(short &_Val){
Get_Int(_Val);
return *this;
}
Fast_Istream &operator>>(int &_Val){
Get_Int(_Val);
return *this;
}
Fast_Istream &operator>>(long &_Val){
Get_Int(_Val);
return *this;
}
Fast_Istream &operator>>(long long &_Val){
Get_Int(_Val);
return *this;
}
Fast_Istream &operator>>(unsigned short &_Val){
Get_Unsigned(_Val);
return *this;
}
Fast_Istream &operator>>(unsigned int &_Val){
Get_Unsigned(_Val);
return *this;
}
Fast_Istream &operator>>(unsigned long &_Val){
Get_Unsigned(_Val);
return *this;
}
Fast_Istream &operator>>(unsigned long long &_Val){
Get_Unsigned(_Val);
return *this;
}
Fast_Istream &operator>>(float &_Val){
Get_Double(_Val);
return *this;
}
Fast_Istream &operator>>(double &_Val){
Get_Double(_Val);
return *this;
}
Fast_Istream &operator>>(long double &_Val){
Get_Double(_Val);
return *this;
}
template <typename Typex,typename... More>
void operator()(Typex &_Val,More &... _More){
*this>>_Val;
operator()(_More...);
}
void pop(){
char ch;
Get_Char(ch);
}
char peek(){
if(_Start_ptr==_End_ptr){
_Start_ptr=_Buf;
_End_ptr=_Buf+inbuf->sgetn(_Buf,Size);
}
if(_Start_ptr==_End_ptr){
_Ok=0;
return -1;
}else{
return *_Start_ptr;
}
}
template <typename Typex>
void operator()(Typex &_Val){
*this>>_Val;
}
template <typename Typex,typename...More>
streambuf *rdbuf(){
return inbuf;
}
void rdbuf(streambuf *_inbuf){
inbuf=_inbuf;
}
Fast_Istream getline(string &s,char _End='\n'){
if(_Ok){
char c;
Get_Char(c);
while((c==32||c==10||c==13||c==8||c==9||c==7||c==12||c==11||c==-1)&&c!=_End){
Get_Char(c);
}
for(s.clear();c!=_End&&~c;Get_Char(c)){
s.push_back(c);
}
--_Start_ptr;
}
return *this;
}
};
}// namespace Fast_I
//快写
namespace Fast_O{
string buf;
streambuf *outbuf;
int _M_precision=6;
struct Fast_Ostream{
Fast_Ostream(streambuf *out,unsigned int Size){
buf.reserve(Size);
outbuf=out;
}
Fast_Ostream(std::streambuf* out){
outbuf=out;
}
Fast_Ostream(const char *File,unsigned int Size){
buf.reserve(Size);
rdbuf(File);
}
void rdbuf(const char *File){
static ofstream __Out__(File);
rdbuf(__Out__.rdbuf());
}
Fast_Ostream(unsigned int Size){
buf.reserve(Size);
}
void flush(){
outbuf->sputn(buf.data(),buf.size());
buf.clear();
}
~Fast_Ostream(){
flush();
}
void endl(){
buf.push_back('\n');
}
Fast_Ostream &operator<<(char _Val){
buf.push_back(_Val);
return *this;
}
Fast_Ostream &operator<<(const char *_Val){
while(*_Val){
buf.push_back(*_Val++);
}
return *this;
}
Fast_Ostream &operator<<(const string &_Val){
buf+=_Val;
return *this;
}
template <typename Typex>
void Put_Unsigned(Typex _Val){
char *_Stack=(char *)malloc(sizeof(Typex)*3);
unsigned S_top=0;
while(_Val){
_Stack[++S_top]=(_Val%10)^48;
_Val/=10;
}
if(!S_top){
buf.push_back('0');
}
while(S_top){
buf.push_back(_Stack[S_top--]);
}
free(_Stack);
}
template <typename Typex>
void Put_Int(Typex _Val){
if(_Val<0){
buf.push_back('-');
Put_Unsigned(~_Val+1);
}else{
Put_Unsigned(_Val);
}
}
Fast_Ostream &operator<<(bool _Val){
buf.push_back(_Val?'1':'0');
return *this;
}
Fast_Ostream &operator<<(short _Val){
Put_Int(_Val);
return *this;
}
Fast_Ostream &operator<<(int _Val){
Put_Int(_Val);
return *this;
}
Fast_Ostream &operator<<(long _Val){
Put_Int(_Val);
return *this;
}
Fast_Ostream &operator<<(long long _Val){
Put_Int(_Val);
return *this;
}
Fast_Ostream &operator<<(unsigned short _Val){
Put_Unsigned(_Val);
return *this;
}
Fast_Ostream &operator<<(unsigned int _Val){
Put_Unsigned(_Val);
return *this;
}
Fast_Ostream &operator<<(unsigned long _Val){
Put_Unsigned(_Val);
return *this;
}
Fast_Ostream &operator<<(unsigned long long _Val){
Put_Unsigned(_Val);
return *this;
}
template <typename Typex>
void endl(const Typex &_Val){
*this<<_Val<<'\n';
}
template <typename Typex,typename... More>
void endl(const Typex &_Val,const More &... _More){
*this<<_Val;
endl(_More...);
}
template <typename Typex>
void operator()(const Typex &_Val){
*this<<_Val;
}
template <typename Typex,typename... More>
void operator()(const Typex &_Val,const More &... _More){
*this<<_Val;
operator()(_More...);
}
std::streambuf *rdbuf(){
return outbuf;
}
void rdbuf(std::streambuf *_outbuf){
outbuf=_outbuf;
}
};
}// namespace Fast_O
namespace Fast_IO{
Fast_I::Fast_Istream fin(cin.rdbuf(),16777216);
Fast_O::Fast_Ostream fout(cout.rdbuf());
}// namespace Fast_IO
#define fin Fast_IO::fin
#define fout Fast_IO::fout
#undef __CLOSE_SYNC
```
## 字符串算法
### 字符串Hash
```cpp
class stringHashC{
private:
constexpr static ull CRCTable[256]={
0ull,4340195606025211873ull,8680391212050423746ull,4921740848265695267ull,8434151890932224675ull,5275782923988786498ull,971319173584276833ull,3549304129150796416ull,
8068624508425914465ull,6035663343856174976ull,1697701945215342499ull,3149153052470335554ull,1942638347168553666ull,2796413900140090659ull,7098608258301592832ull,6825251901632711393ull,
6490467356436725221ull,7361623168864612868ull,2478163407092441639ull,2188552149708172742ull,3395403890430684998ull,1379681698106679463ull,6298306104940671108ull,7733644698202521445ull,
3885276694337107332ull,707133831123647077ull,5592827800280181318ull,8189461293375759783ull,4676819871590606631ull,8997099194556442822ull,4076205395479460069ull,336344856501516036ull,
3586070983360878317ull,1008578063553239308ull,5310510724793993519ull,8469513564492105422ull,4956326814184883278ull,8715327376724315055ull,4377104299416345484ull,37684403149984877ull,
6790807780861369996ull,7063530264788160877ull,2759363396213358926ull,1905095807503912623ull,3112528061657451567ull,1660301244664579022ull,6000793714265887725ull,8033404680093506572ull,
7770553388674214664ull,6335990505171215593ull,1414267662247294154ull,3430340053326002987ull,2223279952962664875ull,2513525083101607498ull,7398390024517330537ull,6527726247848323464ull,
301475225199879017ull,4040985565435702408ull,8960474201025592491ull,4639419168321876810ull,8152410790958920138ull,5555285262125432363ull,672689713003032072ull,3850198703474401769ull,
7172141966721756634ull,6896112701329056315ull,2017156127106478616ull,2865723297506999801ull,1622616839109181305ull,3080402236861542552ull,7994523456615702715ull,5965361108763242330ull,
896517745840219579ull,3479711083407338074ull,8360901865484057209ull,5205205806761112984ull,8754208598832690968ull,4991759417827375353ull,75368806299969754ull,4409230121257379643ull,
4150723131326255167ull,405654209777295326ull,4750353553099509757ull,9067959967341527068ull,5518726792426717852ull,8119159102239575421ull,3810191615007825246ull,638383042291733183ull,
6225056123314903134ull,7663067624797247423ull,3320602489329158044ull,1310088679005751421ull,2553532169166932733ull,2257586620714861852ull,6564284716173382975ull,7431641711380683486ull,
5930354027267144503ull,7960008410874295510ull,3042788754963080437ull,1585637229969582868ull,2828535324494588308ull,1980318352852969077ull,6860680106652005974ull,7137485081799358903ull,
4446559905925329750ull,112064718230027447ull,5027050166203214996ull,8789007311466423157ull,5240354716023005685ull,8395275065003879956ull,3517182702894202423ull,933639166589153750ull,
602950450399758034ull,3775534732870502707ull,8081971130871404816ull,5481889019817449201ull,9030346482859447409ull,4713373941376293776ull,370647126704196531ull,4116208084007846994ull,
7469113332713230003ull,6601406138767999314ull,2292735532829086065ull,2587905371539086992ull,1345379426006064144ull,3355401200587363313ull,7700397406948803538ull,6261752032728566835ull,
4823603603198064275ull,9136564507772074354ull,4217075945466112337ull,485659586792138416ull,4034312254212957232ull,848850972607671249ull,5731446595013999602ull,8336524268413547539ull,
3245233678218362610ull,1239081703546220819ull,6160804473723085104ull,7585447086313631441ull,6342548919878331473ull,7223274949958083504ull,2338409935795303315ull,2038102697739730034ull,
1793035491680439158ull,2655255362396996759ull,6959422166814676148ull,6678747529195019093ull,7921273411411876309ull,5896756564587157044ull,1556264030828725783ull,3000396857132943862ull,
8582637658083885847ull,5413572573028093174ull,1111639976481332437ull,3699195012258665268ull,150737612599939508ull,4480237100512796245ull,8818460242514759286ull,5069379958940844439ull,
8301446262652510334ull,5697002453405118367ull,811308419554590652ull,3997261728307851357ull,448258872920109789ull,4180450932742028604ull,9101344667125017887ull,4788733952703193854ull,
2075361565663127583ull,2375176776549754878ull,7258636602479048669ull,6377276708234557500ull,7620383230015650492ull,6195390427260335453ull,1276766084583466366ull,3282142358086691487ull,
2965177013633572251ull,1521394377481540218ull,5859355848869429849ull,7884648396842094008ull,6641204978658316088ull,6922371643425947865ull,2620177358011502842ull,1758591351447101211ull,
5107064338333865466ull,8855368920738863643ull,4515173241429723704ull,185323563352098265ull,3734556666356615001ull,1146367766414543032ull,5450831443535124635ull,8619404501421971322ull,
2411801801599032137ull,2108537972733056168ull,6417208513977975947ull,7293009827467168618ull,6085577509926160874ull,7516270730994599435ull,3171274459939165736ull,1169204967897651657ull,
5657070648989176616ull,8267073039549717705ull,3960636705705938154ull,778132015414362891ull,4291318829041942923ull,555819988240666218ull,4898546867069886025ull,9205457163736420776ull,
8893119811850659500ull,5139114811686185293ull,224129436460054894ull,4550672333562508943ull,1037680782831563791ull,3629318301239524334ull,8507410736096259021ull,5344396259518358572ull,
1482588506816786125ull,2929677924434714924ull,7846897507062001935ull,5827305377398275822ull,7034365405788404846ull,6747640160261272463ull,1867278333178307500ull,2725415721767562317ull,
1205900900799516068ull,3208604256988987973ull,7551069465741005414ull,6120868271824739719ull,7327383049032621831ull,6452357436695564518ull,2145659414520971461ull,2449273433534943012ull,
9170942131316344261ull,4863539807485053476ull,518840391415781895ull,4253705368048129510ull,741294253408393062ull,3923448753531000967ull,8232416168015693988ull,5621638076290434885ull,
5381517704024256577ull,8544882370750152608ull,3663691524516310915ull,1072829707260485730ull,4585471065658172130ull,259420195707890947ull,5175810743078173984ull,8930449607390606017ull,
2690758852012128288ull,1831845762258155457ull,6710802401174726626ull,6997177456532891651ull,5790325779130739331ull,7809284044625536354ull,2895162889565369665ull,1447581444782684832ull
};
public:
ull BKDRHash(string s,ull seed=131){
ull ans=0;
for(int i=0;i<s.length();i++){
ans=ans*seed+s[i];
}
return ans;
}
ull BKDRHash(char* s,ull seed=131){
ull ans=0;
while(*s){
ans=ans*seed+(*s++);
}
return ans;
}
ull APHash(string s){
ull ans=0;
for(int i=0;i<s.length();i++){
if(i&1){
ans^=~((ans<<11)^s[i]^(ans>>5));
}else{
ans^=(ans<<7)^s[i]^(ans>>3);
}
}
return ans;
}
ull APHash(char* s){
ull ans=0;
for(int i=0;s[i];i++){
if(i&1){
ans^=~((ans<<11)^s[i]^(ans>>5));
}else{
ans^=(ans<<7)^s[i]^(ans>>3);
}
}
return ans;
}
ull JSHash(string s,ull seed=1315423911){
ull ans=seed;
for(int i=0;i<s.length();i++){
ans^=(ans<<5)+s[i]+(ans>>2);
}
return ans;
}
ull JSHash(char* s,ull seed=1315423911){
ull ans=seed;
while(*s){
ans^=(ans<<5)+(*s++)+(ans>>2);
}
return ans;
}
ull RSHash(string s,ull a=63689,ull b=378551){
ull ans=0;
for(int i=0;i<s.length();i++){
ans=ans*a+s[i];
a*=b;
}
return ans;
}
ull RSHash(char* s,ull a=63689,ull b=378551){
ull ans=0;
while(*s){
ans=ans*a+(*s++);
a*=b;
}
return ans;
}
ull SDBMHash(string s){
ull ans=0;
for(int i=0;i<s.length();i++){
ans=s[i]+(ans<<6)+(ans<<16)-ans;
}
return ans;
}
ull SDBMHash(char* s){
ull ans=0;
while(*s){
ans=(*s++)+(ans<<6)+(ans<<16)-ans;
}
return ans;
}
ull PJWHash(string s){
ull ans=0,test=0;
for(int i=0;i<s.length();i++){
ans=(ans<<8)+s[i];
if(test=ans&0xff00000000000000){
ans=((ans^(test>>48))&(0xffffffffffffff));
}
}
return ans;
}
ull PJWHash(char* s){
ull ans=0,test=0;
while(*s){
ans=(ans<<8)+(*s++);
if(test=ans&0xff00000000000000){
ans=((ans^(test>>48))&(0xffffffffffffff));
}
}
return ans;
}
ull ELFHash(string s){
ull ans=0,x=0;
for(int i=0;i<s.length();i++){
ans=(ans<<5)+s[i];
if((x=ans&0xff00000000000000)){
ans^=x>>48;
ans&=~x;
}
}
return ans;
}
ull ELFHash(char* s){
ull ans=0,x=0;
while(*s){
ans=(ans<<5)+(*s++);
if((x=ans&0xff00000000000000)){
ans^=x>>48;
ans&=~x;
}
}
return ans;
}
ull DJBHash(string s){
ull ans=5381;
for(int i=0;i<s.length();i++){
ans+=(ans<<5)+s[i];
}
return ans;
}
ull DJBash(char* s){
ull ans=5381;
while(*s){
ans+=(ans<<5)+(*s++);
}
return ans;
}
ull DEKHash(string s){
ull ans=s.length();
for(int i=0;i<s.length();i++){
ans=(ans<<6)^(ans<<16)^s[i];
}
return ans;
}
ull DEKHash(char* s){
ull ans=0,i=0;
for(;*s;i++){
ans=(ans<<6)^(ans<<16)^s[i];
}
return ans^i;
}
ull BPHash(string s){
ull ans=s.length();
for(int i=0;i<s.length();i++){
ans=(ans<<7)^s[i];
}
return ans;
}
ull BPash(char* s){
ull ans=0,i=0;
for(;*s;i++){
ans=(ans<<7)^(*s++);
}
return ans^i;
}
ull FNVHash(string s,ull seed=0xcbf29ce484222325,ull fnvprime=0x100000001b3){
ull ans=seed;
for(int i=0;i<s.length();i++){
ans^=s[i];
ans*=fnvprime;
}
return ans;
}
ull FNVash(char* s,ull seed=0xcbf29ce484222325,ull fnvprime=0x100000001b3){
ull ans=seed;
while(*s){
ans^=(*s++);
ans*=fnvprime;
}
return ans;
}
ull javaHash(string s){
ull ans=0;
for(int i=0;i<s.length();i++){
ans=ans*31+s[i];
}
return ans;
}
ull javaHash(char* s){
ull ans=0;
while(*s){
ans=ans*31+(*s++);
}
return ans;
}
ull CRCHash(string s,ull seed=0xffffffffffffffffull) {
ull ans=seed;
for(int i=0;i<s.length();i++){
ans=CRCTable[(ans^s[i])&0xff]^(ans>>8);
}
return ans;
}
inline ull fmix64(ull k) {
k^=k>>33;
k*=0xff51afd7ed558ccdull;
k^=k>>33;
k*=0xc4ceb9fe1a85ec53ull;
k^=k>>33;
return k;
}
ull murmurHash(string s,ull seed=27777890035307ull){
ull h1=seed,h2=seed,k1,k2;
constexpr static ull c1=0x87c37b91114253d5ull,c2=0x4cf5ad432745937full;
for(int i=0;i<s.length();i+=2){
k1=s[i];
k2=s[i+1];
k1*=c1;
k1=(k1<<31|k1>>33);
k1*=c2;
h1^=k1;
h1=(h1<<27|h1>>37);
h1+=h2;
h1=h1*5+0x52dce729;
k2*=c2;
k2=(k2<<31|k2>>33);
k2*=c1;
h2^=k2;
h2=(h2<<27|h2>>37);
h2+=h1;
h2=h2*5+0x38495ab5;
}
if(s.length()&1){
k1=*(s.end()-1);
k1*=c1;
k1=(k1<<31|k1>>33);
k1*=c2;
h1^=k1;
h1=(h1<<27|h1>>37);
h1+=h2;
h1=h1*5+0x52dce729;
}
h1^=s.length();
h2^=s.length();
h1+=h2;
h2+=h1;
h1=fmix64(h1);
h2=fmix64(h2);
h1+=h2;
h2+=h1;
return h1+h2;
}
ull murmurHash(char* s,ull seed=27777890035307ull){
ull h1=seed,h2=seed,k1,k2,len=0;
constexpr static ull c1=0x87c37b91114253d5ull,c2=0x4cf5ad432745937full;
while(*s){
k1=*(s++);
k1*=c1;
k1=(k1<<31|k1>>33);
k1*=c2;
h1^=k1;
h1=(h1<<27|h1>>37);
h1+=h2;
h1=h1*5+0x52dce729;
len++;
if(!*s){
break;
}
k2=*(s++);
k2*=c2;
k2=(k2<<31|k2>>33);
k2*=c1;
h2^=k2;
h2=(h2<<27|h2>>37);
h2+=h1;
h2=h2*5+0x38495ab5;
len++;
}
h1^=len;
h2^=len;
h1+=h2;
h2+=h1;
h1=fmix64(h1);
h2=fmix64(h2);
h1+=h2;
h2+=h1;
return h1+h2;
}
};
```
### KMP
```cpp
vector<int> getLPS(string s){
vector<int> LPS(s.length());
for(int i=1,j=0;i<s.length();i++,j=LPS[i-1]){
while(j>0&&s[i]!=s[j]){
j=LPS[j-1];
}
if(s[i]==s[j]){
j++;
}
LPS[i]=j;
}
return LPS;
}
vector<int> stdKMP(string t,string s){
vector<int> LPS=getLPS(t),occurrence;
for(int i=0,j=0;i<s.length();i++){
while(j&&s[i]!=t[j]){
j=LPS[j-1];
}
if(s[i]==t[j]){
j++;
}
if(j==t.length()){
occurrence.push_back(i-j+1);
}
}
return occurrence;
}
vector<int> OIWikiKMP(string t,string s){
string str=t+'\n'+s;
vector<int> LPS=getLPS(str),occurrence;
for(int i=s.length()+1;i<str.length();i++){
if(LPS[i]==s.length()){
occurrence.push_back(i-2*s.length());
}
}
return occurrence;
}
__Pa(vector<int>) getLPSAndOccurrence(string t,string s){
string str=s+'\n'+t;
vector<int> LPS(s.length()),occurrence;
for(int i=1,j=0;i<str.length();i++){
while(j>0&&str[i]!=str[j]){
j=LPS[j-1];
}
if(str[i]==str[j]){
j++;
}
if(i<s.length()){
LPS[i]=j;
}
if(j==s.length()){
occurrence.push_back(i-2*s.length());
}
}
return {LPS,occurrence};
}
```
### Manachar
```cpp
string fillIn(string s){
string ans="#";
for(int i=0;i<s.length();i++){
ans.push_back(s[i]);
ans.push_back('#');
}
return '@'+ans+'`';
}
vector<int> manacher(string str){
string s=fillIn(str);
vector<int> p(s.length());
for(int i=1,r=0,c=0,k;i<s.length();i++){
if(i<r){
k=min(r-i,p[2*c-i]);
}else{
k=1;
}
while(s[i-k]==s[i+k]){
k++;
}
p[i]=k;
if(k+i>r){
r=k+i;
c=i;
}
}
return p;
}
```
## 高精度
### 不压位
```cpp
namespace BigInteger{
class bigInt{
//高精度定义
public:
typedef unsigned short value_type;
typedef const value_type const_value_type;
typedef value_type* pointer;
typedef const_value_type* const_pointer;
typedef value_type& reference;
typedef const_value_type& const_reference;
typedef __gnu_cxx::__normal_iterator<pointer,bigInt> reverse_iterator;
typedef __gnu_cxx::__normal_iterator<const_pointer,bigInt> const_reverse_iterator;
typedef std::reverse_iterator<const_reverse_iterator> const_iterator;
typedef std::reverse_iterator<reverse_iterator> iterator;
iterator begin();
iterator end();
reverse_iterator rbegin();
reverse_iterator rend();
const_iterator cbegin();
const_iterator cend();
const_reverse_iterator crbegin();
const_reverse_iterator crend();
bigInt& constructor(long long);
bigInt& constructor(const std::string&);
bigInt& constructor(const char*);
bigInt(long long=0);
bigInt(const std::string&);
bigInt(const char*);
bigInt(const bigInt&);
~bigInt();
bigInt& operator=(const bigInt&);
bigInt& add(const bigInt&);
bigInt& subtract(const bigInt&);
bigInt& multiply(const bigInt&);
bigInt& add(const long long&);
bigInt& subtract(const long long&);
bigInt& multiply(const long long&);
bigInt& divide(const bigInt&);
bigInt& mod(const bigInt&);
bigInt* divideAndRemainder(const bigInt&);
bigInt& divide(const long long);
bigInt& mod(const long long);
bigInt* divideAndRemainder(const long long);
bigInt& operator+=(const bigInt&);
bigInt& operator-=(const bigInt&);
bigInt& operator*=(const bigInt&);
bigInt& operator/=(const bigInt&);
bigInt& operator%=(const bigInt&);
bigInt& operator+=(const long long);
bigInt& operator-=(const long long);
bigInt& operator*=(const long long);
bigInt& operator/=(const long long);
bigInt& operator%=(const long long);
bigInt& operator++();
bigInt operator++(int);
bigInt& operator--();
bigInt operator--(int);
operator long long();
operator std::string();
operator bool();
bigInt& operator-();
friend bigInt operator+(const bigInt&,const bigInt&);
friend bigInt operator-(const bigInt&,const bigInt&);
friend bigInt operator*(const bigInt&,const bigInt&);
friend bigInt operator/(const bigInt&,const bigInt&);
friend bigInt operator%(const bigInt&,const bigInt&);
friend bigInt operator+(const bigInt&,const long long);
friend bigInt operator-(const bigInt&,const long long);
friend bigInt operator*(const bigInt&,const long long);
friend bigInt operator/(const bigInt&,const long long);
friend bigInt operator%(const bigInt&,const long long);
friend bool operator>(const bigInt&,const bigInt&);
friend bool operator<(const bigInt&,const bigInt&);
friend bool operator>=(const bigInt&,const bigInt&);
friend bool operator<=(const bigInt&,const bigInt&);
friend bool operator==(const bigInt&,const bigInt&);
friend bool operator!=(const bigInt&,const bigInt&);
friend bool operator>(const bigInt&,const long long&);
friend bool operator<(const bigInt&,const long long&);
friend bool operator>=(const bigInt&,const long long&);
friend bool operator<=(const bigInt&,const long long&);
friend bool operator==(const bigInt&,const long long&);
friend bool operator!=(const bigInt&,const long long&);
friend std::istream& operator>>(std::istream&,bigInt&);
friend std::ostream& operator<<(std::ostream&,const bigInt&);
unsigned short& operator[](size_t);
long long toInteger(bool=1) const;
std::string toString() const;
bool toBoolean() const;
size_t length() const;
size_t size() const;
int compare(const bigInt&) const;
void swap(bigInt&);
void clear();
void resize(size_t);
void setpositive(bool);
void pop();
void push(const unsigned short);
bool empty();
unsigned short front();
unsigned short back();
private:
unsigned short *__num=nullptr;
size_t __num_length=0,__num_size=0;
bool __flag=1;
bigInt **__new_bi_location=nullptr;
size_t __new_bi_location_length=0,__new_bi_location_size=0;
void __location_push(bigInt*);
size_t __newsize(unsigned short*&,size_t);
size_t __resize(unsigned short*&,size_t,size_t);
void __add(const bigInt&,const bigInt&,bigInt&);
void __subtract(const bigInt&,const bigInt&,bigInt&);
void __multiply(const bigInt&,const bigInt&,bigInt&);
void __divide_mod_bi(const bigInt&,const bigInt&,bigInt&,bigInt&);
void __divide_mod_li(const bigInt&,const long long,bigInt&,bigInt&);
};
//高精度实现
bigInt::iterator bigInt::begin(){
return iterator(this->rend());
}
bigInt::iterator bigInt::end(){
this->__num[-1]=0;
return iterator(this->rbegin());
}
bigInt::reverse_iterator bigInt::rbegin(){
return reverse_iterator(this->__num);
}
bigInt::reverse_iterator bigInt::rend(){
this->__num[this->__num_length]=0;
return reverse_iterator(this->__num+this->__num_length);
}
bigInt::const_iterator bigInt::cbegin(){
return const_iterator(this->crend());
}
bigInt::const_iterator bigInt::cend(){
this->__num[-1]=0;
return const_iterator(this->crbegin());
}
bigInt::const_reverse_iterator bigInt::crbegin(){
return const_reverse_iterator(this->__num);
}
bigInt::const_reverse_iterator bigInt::crend(){
this->__num[this->__num_length]=0;
return const_reverse_iterator(this->__num+this->__num_length);
}
bigInt& bigInt::constructor(long long num){
if(this->__num_size<20){
this->__num_size=this->__newsize(this->__num,20);
}
this->__num_length=0;
if(!num){
this->__flag=1;
this->__num[this->__num_length++]=0;
}else{
if(num<0){
this->__flag=0;
num=-num;
}else{
this->__flag=1;
}
while(num){
this->__num[this->__num_length++]=num%10;
num/=10;
}
}
return *this;
}
bigInt& bigInt::constructor(const std::string &str){
int start_index=0,str_length=str.length();
if(str[0]=='-'){
this->__flag=0;
start_index++;
}else{
this->__flag=1;
}
while(str[start_index]=='0'){
start_index++;
}
if(this->__num_size<str_length-start_index+1){
this->__num_size=this->__newsize(this->__num,str_length-start_index+1);
}
this->__num_length=0;
for(int i=str_length-1;i>=start_index;i--){
this->__num[this->__num_length++]=str[i]-'0';
}
if(!this->__num_length){
this->__num[this->__num_length++]=0;
}
return *this;
}
bigInt& bigInt::constructor(const char *str){
int start_index=0,str_length=strlen(str);
if(str[0]=='-'){
this->__flag=0;
start_index++;
}else{
this->__flag=1;
}
while(str[start_index]=='0'){
start_index++;
}
if(this->__num_size<str_length-start_index+1){
this->__num_size=this->__newsize(this->__num,str_length-start_index+1);
}
this->__num_length=0;
for(int i=str_length-1;i>=start_index;i--){
this->__num[this->__num_length++]=str[i]-'0';
}
if(!this->__num_length){
this->__num[this->__num_length++]=0;
}
return *this;
}
bigInt::bigInt(long long num){
this->constructor(num);
}
bigInt::bigInt(const std::string &str){
this->constructor(str);
}
bigInt::bigInt(const char *str){
this->constructor(str);
}
bigInt::bigInt(const bigInt &bi){
this->__num_size=this->__newsize(this->__num,bi.__num_size);
memcpy(this->__num,bi.__num,bi.__num_length*sizeof(unsigned short));
this->__num_length=bi.__num_length;
this->__flag=bi.__flag;
}
bigInt::~bigInt(){
delete[] this->__num;
for(size_t i=0;i<this->__new_bi_location_length;i++){
delete[] this->__new_bi_location[i];
}
delete[] this->__new_bi_location;
}
bigInt& bigInt::operator=(const bigInt &bi){
this->__num_size=this->__newsize(this->__num,bi.__num_size);
memcpy(this->__num,bi.__num,bi.__num_length*sizeof(unsigned short));
this->__num_length=bi.__num_length;
this->__flag=bi.__flag;
return *this;
}
bigInt& bigInt::operator-(){
if(!(this->__num_length==1&&this->__num[0]==0)){
this->__flag=!this->__flag;
}
return *this;
}
bigInt& bigInt::add(const bigInt &bi){
if(bi.__flag==this->__flag){
this->__add(*this,bi,*this);
}else if(bi.__flag){
this->__flag=1;
this->swap(bigInt(bi).subtract(*this));
}else{
bigInt &bi_map=const_cast<bigInt&>(bi);
bi_map.__flag=1;
this->subtract(bi_map);
bi_map.__flag=0;
}
return *this;
}
bigInt& bigInt::add(const long long &bi){
return this->add(bigInt(bi));
}
bigInt& bigInt::subtract(const bigInt &bi){
if(bi.__flag==this->__flag){
int _cmp=this->compare(bi);
if(_cmp>0){
if(this->__flag){
this->__subtract(*this,bi,*this);
}else{
this->__subtract(bi,*this,*this);
}
this->__flag=1;
}else if(_cmp<0){
if(this->__flag){
this->__subtract(bi,*this,*this);
}else{
this->__subtract(*this,bi,*this);
}this->__flag=0;
}else{
this->clear();
}
}else{
this->__add(*this,bi,*this);
}
return *this;
}
bigInt& bigInt::subtract(const long long &bi){
return this->subtract(bigInt(bi));
}
bigInt& bigInt::multiply(const bigInt &bi){
if(this->__num_length==1&&this->__num[0]==0||bi.__num_length==1&&bi.__num[0]==0){
this->clear();
}else if(this->__num_length==1&&this->__num[0]==1){
bool this_flag=this->__flag;
bigInt ans(bi);
this->swap(ans);
this->__flag=bi.__flag?this_flag:!this_flag;
}else if(bi.__num_length==1&&bi.__num[0]==1){
this->__flag=bi.__flag?this->__flag:!this->__flag;
return *this;
}else{
bool this_flag=this->__flag;
this->__multiply(*this,bi,*this);
this->__flag=this_flag!=bi.__flag?0:1;
}
return *this;
}
bigInt& bigInt::multiply(const long long &bi){
return this->multiply(bigInt(bi));
}
bigInt& bigInt::divide(const bigInt &bi){
if(bi.__num_length==1&&bi.__num[0]==1){
this->__flag=bi.__flag==this->__flag;
}else{
this->swap(this->divideAndRemainder(bi)[0]);
}
return *this;
}
bigInt& bigInt::mod(const bigInt &bi){
if(bi.__num_length==1&&bi.__num[0]==1){
this->clear();
}else{
this->swap(this->divideAndRemainder(bi)[1]);
}
return *this;
}
bigInt* bigInt::divideAndRemainder(const bigInt &bi){
bigInt* ans=new bigInt[2];
this->__location_push(ans);
if(bi.__num_length==1&&bi.__num[0]==0){
abort();
}
if(bi.__num_length==1&&bi.__num[0]==1){
bigInt temp(*this);
ans[0].swap(temp);
ans[0].__flag=bi.__flag==this->__flag;
}else{
bool this_flag=this->__flag;
if(bi.__flag!=this->__flag){
this->__flag=bi.__flag;
}
int _cmp=this->compare(bi);
if(_cmp>0){
if(bi.__flag){
this->__divide_mod_bi(*this,bi,ans[0],ans[1]);
ans[0].__flag=this_flag==bi.__flag;
ans[1].__flag=this_flag;
}else{
bigInt temp(*this);
ans[1].swap(temp);
}
}else if(_cmp<0){
if(bi.__flag){
bigInt temp(*this);
ans[1].swap(temp);
}else{
this->__divide_mod_bi(*this,bi,ans[0],ans[1]);
ans[0].__flag=this_flag==bi.__flag;
ans[1].__flag=this_flag;
}
}else{
ans[0]=this_flag==bi.__flag?1:-1;
}
this->__flag=this_flag;
}
return ans;
}
bigInt& bigInt::divide(const long long li){
if(li==1||li==-1){
this->__flag=li>0?this->__flag:!this->__flag;
}else{
this->swap(this->divideAndRemainder(li)[0]);
}
return *this;
}
bigInt& bigInt::mod(const long long li){
if(li==1||li==-1){
this->clear();
}else{
this->swap(this->divideAndRemainder(li)[1]);
}
return *this;
}
bigInt* bigInt::divideAndRemainder(const long long li){
bigInt* ans=new bigInt[2];
this->__location_push(ans);
if(li==0){
abort();
}
bool li_flag=li>0;
if(li==1||li==-1){
bigInt temp(*this);
ans[0].swap(temp);
ans[0].__flag=li_flag==this->__flag;
}else{
bigInt bi(li);
if(bi.length()>18){
this->__divide_mod_bi(*this,bi,ans[0],ans[1]);
}else{
this->__divide_mod_li(*this,(li>0?li:-li),ans[0],ans[1]);
}
ans[0].__flag=this->__flag==li_flag;
ans[1].__flag=this->__flag;
}
return ans;
}
bigInt& bigInt::operator+=(const bigInt &bi){
this->add(bi);
return *this;
}
bigInt& bigInt::operator-=(const bigInt &bi){
this->subtract(bi);
return *this;
}
bigInt& bigInt::operator*=(const bigInt &bi){
this->multiply(bi);
return *this;
}
bigInt& bigInt::operator/=(const bigInt &bi){
this->divide(bi);
return *this;
}
bigInt& bigInt::operator%=(const bigInt &bi){
this->mod(bi);
return *this;
}
bigInt& bigInt::operator+=(const long long li){
this->add(li);
return *this;
}
bigInt& bigInt::operator-=(const long long li){
this->subtract(li);
return *this;
}
bigInt& bigInt::operator*=(const long long li){
this->multiply(li);
return *this;
}
bigInt& bigInt::operator/=(const long long li){
this->divide(li);
return *this;
}
bigInt& bigInt::operator%=(const long long li){
this->mod(li);
return *this;
}
bigInt& bigInt::operator++(){
this->add(1);
return *this;
}
bigInt bigInt::operator++(int){
bigInt ans(*this);
this->add(1);
return *this;
}
bigInt& bigInt::operator--(){
this->subtract(1);
return *this;
}
bigInt bigInt::operator--(int){
bigInt ans(*this);
this->subtract(1);
return *this;
}
bigInt::operator long long(){
return this->toInteger(0);
}
bigInt::operator std::string(){
return this->toString();
}
bigInt::operator bool(){
return this->toBoolean();
}
bigInt operator+(const bigInt &bi_a,const bigInt &bi_b){
bigInt ans(bi_a);
ans.add(bi_b);
return ans;
}
bigInt operator-(const bigInt &bi_a,const bigInt &bi_b){
bigInt ans(bi_a);
ans.subtract(bi_b);
return ans;
}
bigInt operator*(const bigInt &bi_a,const bigInt &bi_b){
bigInt ans(bi_a);
ans.multiply(bi_b);
return ans;
}
bigInt operator/(const bigInt &bi_a,const bigInt &bi_b){
bigInt ans(bi_a);
ans.divide(bi_b);
return ans;
}
bigInt operator%(const bigInt &bi_a,const bigInt &bi_b){
bigInt ans(bi_a);
ans.mod(bi_b);
return ans;
}
bigInt operator+(const bigInt &bi_a,const long long &li_b){
bigInt ans(bi_a);
ans.add(li_b);
return ans;
}
bigInt operator-(const bigInt &bi_a,const long long &li_b){
bigInt ans(bi_a);
ans.subtract(li_b);
return ans;
}
bigInt operator*(const bigInt &bi_a,const long long &li_b){
bigInt ans(bi_a);
ans.multiply(li_b);
return ans;
}
bigInt operator/(const bigInt &bi_a,const long long li_b){
bigInt ans(bi_a);
ans.divide(li_b);
return ans;
}
bigInt operator%(const bigInt &bi_a,const long long li_b){
bigInt ans(bi_a);
ans.mod(li_b);
return ans;
}
bool operator>(const bigInt &bi_a,const bigInt &bi_b){
return bi_a.compare(bi_b)>0;
}
bool operator<(const bigInt &bi_a,const bigInt &bi_b){
return bi_a.compare(bi_b)<0;
}
bool operator>=(const bigInt &bi_a,const bigInt &bi_b){
int _cmp=bi_a.compare(bi_b);
return(_cmp==1||_cmp==0);
}
bool operator<=(const bigInt &bi_a,const bigInt &bi_b){
int _cmp=bi_a.compare(bi_b);
return(_cmp==-1||_cmp==0);
}
bool operator==(const bigInt &bi_a,const bigInt &bi_b){
return bi_a.compare(bi_b)==0;
}
bool operator!=(const bigInt &bi_a,const bigInt &bi_b){
return !(bi_a.compare(bi_b)==0);
}
bool operator>(const bigInt &bi_a,const long long &li_b){
return bi_a.compare(li_b)>0;
}
bool operator<(const bigInt &bi_a,const long long &li_b){
return bi_a.compare(li_b)<0;
}
bool operator>=(const bigInt &bi_a,const long long &li_b){
int _cmp=bi_a.compare(li_b);
return(_cmp==1||_cmp==0);
}
bool operator<=(const bigInt &bi_a,const long long &li_b){
int _cmp=bi_a.compare(li_b);
return(_cmp==-1||_cmp==0);
}
bool operator==(const bigInt &bi_a,const long long &li_b){
return bi_a.compare(li_b)==0;
}
bool operator!=(const bigInt &bi_a,const long long &li_b){
return !(bi_a.compare(li_b)==0);
}
std::istream& operator>>(std::istream& _cin,bigInt &bi){
std::string str;
_cin>>str;
bi.constructor(str);
return _cin;
}
std::ostream& operator<<(std::ostream& _cout,const bigInt &bi){
if(!bi.__flag){
_cout<<'-';
}
for(int i=bi.__num_length-1;i>=0;i--){
_cout<<bi.__num[i];
}
return _cout;
}
unsigned short& bigInt::operator[](size_t index){
return this->__num[this->__num_length-index-1];
}
long long bigInt::toInteger(bool check_overflow) const{
if(!check_overflow||(this->__num_length<19||(this->__num_length==19&&(this->__flag?this->compare(bigInt("9223372036854775807"))<=0:this->compare(bigInt("-9223372036854775807"))>=0)))){
long long ans=0,cnt=1;
for(int i=0;i<this->__num_length;i++,cnt*=10){
ans+=cnt*this->__num[i];
}
return this->__flag?ans:-ans;
}else{
return 0LL;
}
}
std::string bigInt::toString() const{
std::string ans;
if(!this->__flag){
ans.push_back('-');
}
for(int i=this->__num_length-1;i>=0;i--){
ans.push_back(this->__num[i]+'0');
}
return ans;
}
bool bigInt::toBoolean() const{
return !(this->__num_length==1&&this->__num[0]==0);
}
size_t bigInt::length() const{
return this->__num_length;
}
size_t bigInt::size() const{
return this->__num_size;
}
void bigInt::pop(){
if(this->__num_length>1){
this->__num_length--;
}else{
this->clear();
}
}
void bigInt::push(const unsigned short num){
if(this->__num_length==1&&this->__num[0]==0){
this->__num_length--;
}
if(this->__num_length>=this->__num_size){
this->__num_size=(size_t)(this->__num_size*1.5);
this->__num_size=this->__resize(this->__num,this->__num_size==1?2:this->__num_size,this->__num_length);
}
this->__num[this->__num_length++]=num;
}
bool bigInt::empty(){
return this->__num_length==1&&this->__num[0]==0;
}
unsigned short bigInt::front(){
return this->__num[this->__num_length-1];
}
unsigned short bigInt::back(){
return this->__num[0];
}
int bigInt::compare(const bigInt &bi) const{
if(this->__flag!=bi.__flag){
return this->__flag?1:-1;
}else{
int ans=this->__flag?1:-1;
if(this->__num_length>bi.__num_length){
return ans;
}else if(this->__num_length<bi.__num_length){
return -ans;
}else{
for(int i=this->__num_length-1;i>=0;i--){
if(this->__num[i]<bi.__num[i]){
return -ans;
}else if(this->__num[i]>bi.__num[i]){
return ans;
}
}
return 0;
}
}
}
void bigInt::swap(bigInt &bi){
std::swap(this->__flag,bi.__flag);
std::swap(this->__num_size,bi.__num_size);
std::swap(this->__num_length,bi.__num_length);
std::swap(this->__num,bi.__num);
std::swap(this->__new_bi_location_size,bi.__new_bi_location_size);
std::swap(this->__new_bi_location_length,bi.__new_bi_location_length);
std::swap(this->__new_bi_location,bi.__new_bi_location);
}
void bigInt::clear(){
this->__num_length=1;
this->__num[0]=0;
this->__flag=1;
}
void bigInt::resize(size_t size){
this->__num_size=this->__resize(this->__num,size,this->__num_size);
this->__num_length=min(this->__num_size,this->__num_length);
}
void bigInt::setpositive(bool flag){
if(this->__num_length==1&&this->__num[0]==0){
return;
}
this->__flag=flag;
}
void bigInt::__location_push(bigInt* new_bi_location){
if(this->__new_bi_location_length>=this->__new_bi_location_size){
this->__new_bi_location_size*=1.5;
this->__new_bi_location_size=this->__new_bi_location_size?this->__new_bi_location_size:4;
bigInt** new_bi_location_list=new bigInt* [this->__new_bi_location_size]{NULL};
memcpy(new_bi_location_list,this->__new_bi_location,this->__new_bi_location_length*sizeof(bigInt*));
delete[] this->__new_bi_location;
this->__new_bi_location=new_bi_location_list;
}
this->__new_bi_location[this->__new_bi_location_length++]=new_bi_location;
}
size_t bigInt::__newsize(unsigned short*& num,size_t length){
delete[] num;
num=new unsigned short[length]{0};
return length;
}
size_t bigInt::__resize(unsigned short*& num,size_t length,size_t prelen){
unsigned short* new_num=new unsigned short[length]{0};
memcpy(new_num,num,(prelen>length?length:prelen)*sizeof(unsigned short));
delete[] num;
num=new_num;
return length;
}
void bigInt::__add(const bigInt &a,const bigInt &b,bigInt &c){
int a_length=a.__num_length,b_length=b.__num_length,min_length=a_length<b_length?(b_length+1>c.__num_size?(c.__num_size=this->__resize(c.__num,b_length+1,c.__num_length)):0,a_length):(a_length+1>c.__num_size?(c.__num_size=this->__resize(c.__num,a_length+1,c.__num_length)):0,b_length);
c.__num_length=0;
unsigned short sum,t=0;
for(int i=0;i<min_length;i++){
sum=a.__num[i]+b.__num[i]+t;
t=sum/10;
c.__num[c.__num_length++]=sum%10;
}
if(a_length>b_length){
for(int i=min_length;i<a_length;i++){
sum=a.__num[i]+t;
t=sum/10;
c.__num[c.__num_length++]=sum%10;
}
}else if(a_length<b_length){
for(int i=min_length;i<b_length;i++){
sum=b.__num[i]+t;
t=sum/10;
c.__num[c.__num_length++]=sum%10;
}
}
if(t){
c.__num[c.__num_length++]=t;
}
}
void bigInt::__subtract(const bigInt &a,const bigInt &b,bigInt &c){
int a_length=a.__num_length,b_length=b.__num_length;
if(c.__num_size<a_length){
c.__num_size=this->__resize(c.__num,a_length,c.__num_size);
}
c.__num_length=0;
short sum,t=0;
for(int i=0;i<b_length;i++){
sum=a.__num[i]-b.__num[i]-t;
t=0;
c.__num[c.__num_length++]=sum>=0?sum:(t=1,sum+10);
}
if(a_length!=b_length){
for(int i=b_length;i<a_length;i++){
sum=a.__num[i]-t;
t=0;
c.__num[c.__num_length++]=sum>=0?sum:(t=1,sum+10);
}
}
while(c.__num_length>1&&c.__num[c.__num_length-1]==0){
c.__num_length--;
}
}
void bigInt::__multiply(const bigInt &a,const bigInt &b,bigInt &c){
int a_length=a.__num_length,b_length=b.__num_length;
bigInt ans;
ans.__num_size=this->__newsize(ans.__num,a_length+b_length+1);
ans.__num_length=a_length+b_length;
unsigned short t;
for(int i=0;i<a_length;i++){
t=0;
for(int j=0;j<b_length;j++){
ans.__num[i+j]=a.__num[i]*b.__num[j]+ans.__num[i+j]+t;
t=ans.__num[i+j]/10;
ans.__num[i+j] %= 10;
}
ans.__num[b_length+i]=t;
}
while(ans.__num_length>1&&ans.__num[ans.__num_length-1]==0){
ans.__num_length--;
}
c.swap(ans);
}
void bigInt::__divide_mod_bi(const bigInt &a,const bigInt &b,bigInt ÷r,bigInt &remainder){
bigInt temp,cp_a(a);
temp.__num_size=this->__newsize(temp.__num,a.__num_length+b.__num_length+1);
remainder.swap(cp_a);
temp.__flag=remainder.__flag=1;
size_t prelen=divider.__num_length;
divider.__num_length=a.__num_length-b.__num_length+1;
if(divider.__num_length>divider.__num_size){
divider.__num_size=this->__resize(divider.__num,divider.__num_length+1,prelen);
}
for(int i=divider.__num_length-1;i>=0;i--){
memset(temp.__num,0,sizeof(i+b.__num_length));
for(size_t j=0;j<b.__num_length;j++){
temp.__num[j+i]=b.__num[j];
}
temp.__num_length=b.__num_length+i;
while(remainder.compare(temp)>=0){
divider.__num[i]++;
this->__subtract(remainder,temp,remainder);
}
}
while(divider.__num_length>1&÷r.__num[divider.__num_length-1]==0){
divider.__num_length--;
}
}
void bigInt::__divide_mod_li(const bigInt &a,const long long b,bigInt ÷r,bigInt &remainder){
long long t=0;
divider.__num_length=a.__num_length;
divider.__num_size=this->__newsize(divider.__num,divider.__num_length+1);
for(int i=divider.__num_length-1;i>=0;i--){
divider.__num[i]=(t*10+a.__num[i])/b;
t=(t*10+a.__num[i])%b;
}
while(divider.__num_length>1&÷r.__num[divider.__num_length-1]==0){
divider.__num_length--;
}
bigInt ans(t);
remainder.swap(ans);
}
}
```
### 压位
```cpp
class ZeroDivisionError:public std::runtime_error{
public:
ZeroDivisionError():runtime_error("Division by zero"){}
};
class FFTLimitExceededError:public std::runtime_error{
public:
FFTLimitExceededError():runtime_error("FFT size limit exceeded"){}
};
class NegativeRadicandError:public std::runtime_error{
public:
NegativeRadicandError():runtime_error("Negative radicand in root operation"){}
};
class BigInteger{
protected:
static constexpr int WIDTH=8;
static constexpr long long BASE=1e8;
static constexpr long long FFT_LIMIT=32;
static constexpr long long NEWTON_DIV_LIMIT=64;
static constexpr long long NEWTON_DIV_MIN_LEVEL=16;
static constexpr long long NEWTON_SQRT_LIMIT=48;
static constexpr long long NEWTON_SQRT_MIN_LEVEL=5;
static constexpr size_t POOL_CHUNK_SIZE=1024;
long long* digits;
int capacity,size;
bool flag;
inline void push(const long long&);
inline void pop();
inline void resize(const int&);
inline int compare(const BigInteger&)const;
inline int compare(const long long&)const;
BigInteger& build_binary(const std::vector<bool>&);
static inline BigInteger fft_mul(const BigInteger&,const BigInteger&);
BigInteger newton_inv(int)const;
std::pair<BigInteger,BigInteger> newton_div(const BigInteger&)const;
BigInteger newton_invsqrt()const;
BigInteger sqrt_normal()const;
std::vector<long long*> memory_pool;
inline long long*allocate_digits(size_t);
inline void deallocate_digits(long long*,size_t);
public:
void reserve(const int&);
void clear();
~BigInteger()=default;
int _digit_len()const;
friend std::ostream&operator<<(std::ostream& out,const BigInteger& x){
if(!x.flag){
out<<'-';
}
out<<x.digits[x.size];
for(int i=x.size-1;i>=1;i--){
out<<std::setw(WIDTH)<<std::setfill('0')<<x.digits[i];
}
return out;
}
friend std::istream&operator>>(std::istream& in,BigInteger& x){
std::string s;
in>>s;
x=s;
return in;
}
BigInteger():digits(nullptr),flag(1){
*this=0ll;
}
BigInteger(const BigInteger& x):digits(nullptr){
*this=x;
}
BigInteger(const long long& x):digits(nullptr){
*this=x;
}
BigInteger(const std::string&s):digits(nullptr){
*this=s;
}
BigInteger(const std::vector<bool>&b):digits(nullptr){
*this=b;
}
template<class T> BigInteger(const T&begin,const T&end):digits(nullptr){
*this=std::vector<bool>(begin,end);
}
BigInteger(const long long*in,int len):digits(nullptr),flag(1){
while(len>0&&in[len-1]==0){
len--;
in++;
}
size=len;
digits=allocate_digits(len+1);
for(int i=0;i<len;i++){
digits[i+1]=in[i];
}
}
BigInteger& operator=(const BigInteger&);
BigInteger& operator=(const long long&);
BigInteger& operator=(const std::string&);
BigInteger& operator=(const std::vector<bool>&);
BigInteger& operator=(const __int128&);
std::string to_string()const;
long long to_long_long()const;
std::vector<bool> to_binary()const;
__int128 to_int128()const;
BigInteger operator-()const;
BigInteger operator~()const;
BigInteger abs()const;
operator std::string()const;
operator long long()const;
operator std::vector<bool>()const;
operator __int128()const;
bool operator==(const BigInteger&)const;
bool operator!=(const BigInteger&)const;
bool operator>=(const BigInteger&)const;
bool operator<=(const BigInteger&)const;
bool operator>(const BigInteger&)const;
bool operator<(const BigInteger&)const;
bool operator==(const long long&)const;
bool operator!=(const long long&)const;
bool operator>=(const long long&)const;
bool operator<=(const long long&)const;
bool operator>(const long long&)const;
bool operator<(const long long&)const;
#if __cplusplus>201703L
auto operator<=> (const BigInteger&)const;
auto operator<=> (const long long&)const;
#endif
BigInteger div2()const;
std::pair<BigInteger,BigInteger> divmod(const BigInteger&,bool=false)const;
BigInteger operator+(const long long&)const;
BigInteger operator+(const BigInteger&)const;
BigInteger operator-(const long long&)const;
BigInteger operator-(const BigInteger&)const;
BigInteger operator*(const long long&)const;
BigInteger operator*(const BigInteger&)const;
BigInteger operator/(const long long&)const;
BigInteger operator/(const BigInteger&)const;
BigInteger operator%(const long long&)const;
BigInteger operator%(const BigInteger&)const;
BigInteger pow(const long long&)const;
template<typename T> BigInteger pow(const long long&,const T&)const;
BigInteger root(const long long& =2)const;
BigInteger sqrt()const;
BigInteger gcd(const BigInteger&)const;
BigInteger lcm(const BigInteger&)const;
inline BigInteger _move_l(int)const;
inline BigInteger _move_r(int)const;
BigInteger& operator+=(const long long&);
BigInteger& operator+=(const BigInteger&);
BigInteger& operator-=(const long long&);
BigInteger& operator-=(const BigInteger&);
BigInteger& operator*=(long long);
BigInteger& operator*=(const BigInteger&);
BigInteger& operator/=(const long long&);
BigInteger& operator/=(const BigInteger&);
BigInteger& operator%=(const long long&);
BigInteger& operator%=(const BigInteger&);
BigInteger operator<<(const long long&);
BigInteger operator>>(const long long&);
BigInteger& operator<<=(const long long&);
BigInteger& operator>>=(const long long&);
BigInteger operator&(const BigInteger&);
BigInteger operator|(const BigInteger&);
BigInteger operator^(const BigInteger&);
BigInteger& operator&=(const BigInteger&);
BigInteger& operator|=(const BigInteger&);
BigInteger& operator^=(const BigInteger&);
BigInteger& operator++();
BigInteger operator++(int);
BigInteger& operator--();
BigInteger operator--(int);
static BigInteger random(const int&);
};
inline void BigInteger::push(const long long& val){
if(size==capacity){
int new_capacity=(capacity<256)?capacity*2:static_cast<int>(std::pow(capacity,1.125));
long long*new_digits=allocate_digits(new_capacity+1);
memcpy(new_digits,digits,sizeof(long long)*(capacity+1));
deallocate_digits(digits,capacity+1);
digits=new_digits;
capacity=new_capacity;
}
digits[++size]=val;
}
inline void BigInteger::pop(){
digits[size--]=0;
}
inline void BigInteger::resize(const int&sz){
reserve(sz);
size=sz;
}
inline int BigInteger::compare(const BigInteger& x)const{
if(flag&&!x.flag){
return 1;
}
if(!flag&&x.flag){
return-1;
}
int sgn=(flag&&x.flag?1:-1);
if(size>x.size){
return sgn;
}
if(size<x.size){
return -sgn;
}
for(int i=size;i>=1;i--){
if(digits[i]>x.digits[i]){
return sgn;
}
if(digits[i]<x.digits[i]){
return -sgn;
}
}
return 0;
}
inline int BigInteger::compare(const long long& x)const{
if(flag&&x>=0){
return 1;
}
if(!flag&&x<0){
return -1;
}
int sgn=(flag&&x<0?1:-1);
std::string s=std::to_string(x);
if(size>s.length()-(x<0)){
return sgn;
}
if(size<s.length()-(x<0)){
return -sgn;
}
for(int i=size;i>=1;i--){
if(digits[i]>s[i-1]-'0'){
return sgn;
}
if(digits[i]<s[i-1]-'0'){
return -sgn;
}
}
return 0;
}
BigInteger& BigInteger::build_binary(const std::vector<bool>&b){
*this=0ll;
if(b.empty()||(b.size()==1&&b[0]==0)){
return *this;
}
BigInteger pw2=1;
for(int i=b.size()-1;i>=0;i--,pw2+=pw2){
if(b[i]){
*this+=pw2;
}
}
return *this;
}
inline long long*BigInteger::allocate_digits(size_t size){
for(auto it=memory_pool.begin();it!=memory_pool.end();++it){
size_t*block_size=reinterpret_cast<size_t*>(*it)-1;
if(*block_size>=size){
long long*block=*it;
memory_pool.erase(it);
memset(block,0,size*sizeof(long long));
return block;
}
}
size_t*mem=static_cast<size_t*>(::operator new(sizeof(size_t)+size*sizeof(long long)));
*mem=size;
long long*ptr=reinterpret_cast<long long*>(mem+1);
memset(ptr,0,size*sizeof(long long));
return ptr;
}
inline void BigInteger::deallocate_digits(long long*ptr,size_t size){
if(!ptr){
return;
}
size_t*block_size=reinterpret_cast<size_t*>(ptr)-1;
if(*block_size>=POOL_CHUNK_SIZE){
memory_pool.push_back(ptr);
}else{
::operator delete(block_size);
}
}
void BigInteger::reserve(const int&sz){
if(sz<0){
return;
}
if(digits!=nullptr){
deallocate_digits(digits,capacity+1);
}
capacity=sz;
size=0;
digits=allocate_digits(sz+1);
}
void BigInteger::clear(){
deallocate_digits(digits,capacity+1);
digits=nullptr;
size=capacity=0;
}
int BigInteger::_digit_len()const{
return size;
}
BigInteger& BigInteger::operator=(const BigInteger& x){
if(this!=&x){
long long*new_digits=allocate_digits(x.size+1);
deallocate_digits(digits,capacity+1);
digits=new_digits;
capacity=x.size;
flag=x.flag;
size=x.size;
memcpy(digits,x.digits,sizeof(long long)*(x.size+1));
}
return *this;
}
BigInteger& BigInteger::operator=(const long long& x){
flag=(x>=0),reserve(4);
if(x==0){
return size=1,digits[1]=0,*this;
}
if(x==LLONG_MIN){
return *this="-9223372036854775808";
}
long long n=std::abs(x);
do{
push(n%BASE),n/=BASE;
}while(n);
return *this;
}
BigInteger& BigInteger::operator=(const std::string&s){
flag=1,reserve(s.size()/WIDTH+1);
if(s.empty()||s=="-"){
return*this=0ll;
}
int i=0;
if(s[0]=='-'){
flag=false,i++;
}
for(int j=s.size()-1;j>=i;j-=WIDTH){
int start=std::max(i,j-WIDTH+1),len=j-start+1;
push(stoll(s.substr(start,len)));
}
while(size>1&&digits[size]==0){
pop();
}
return *this;
}
BigInteger& BigInteger::operator=(const std::vector<bool>&a){
if(a==std::vector<bool>{0ll}) return*this=0ll;
std::vector<bool> res;
if(a[0]==0){
return build_binary(a);
}
res.resize(a.size());
for(int i=0;i<(int) a.size();++i){
res[i]=!a[i];
}
BigInteger x;
x.build_binary(res);
return *this=-x-1;
}
BigInteger& BigInteger::operator=(const __int128&x){
flag=(x>=0),reserve(8);
if(x==0){
return size=1,digits[1]=0,*this;
}
__int128 n=x>=0?x:-x;
do{
push(n%BASE);
n/=BASE;
}while(n);
return *this;
}
std::string BigInteger::to_string()const{
std::stringstream ss;
ss<<*this;
return ss.str();
}
long long BigInteger::to_long_long()const{
return stoll(to_string());
}
std::vector<bool> BigInteger::to_binary()const{
if(*this==0)
return{0,0};
std::vector<bool> res;
if(flag){
for(BigInteger x=*this;x!=0;x=x.div2()){
res.emplace_back(x.digits[1]&1);
}
res.emplace_back(0);
reverse(res.begin(),res.end());
return res;
}else{
for(BigInteger x=-*this-1;x!=0;x=x.div2()){
res.emplace_back(!(x.digits[1]&1));
}
res.emplace_back(1);
reverse(res.begin(),res.end());
return res;
}
};
__int128 BigInteger::to_int128()const{
__int128 res=0;
for(int i=size;i>=1;i--){
res=res*BASE+digits[i];
}
return res;
}
BigInteger BigInteger::operator-()const{
if(*this==0){
return 0;
}
BigInteger res=*this;
res.flag=!flag;
return res;
}
BigInteger BigInteger::operator~()const{
return -(*this)-1ll;
}
BigInteger BigInteger::abs()const{
BigInteger res=*this;
res.flag=1;
return res;
}
BigInteger::operator std::string()const{
std::stringstream ss;
ss<<*this;
return ss.str();
}
BigInteger::operator long long()const{
return stoll(to_string());
}
BigInteger::operator std::vector<bool>()const{
if(*this==0)
return{0,0};
std::vector<bool> res;
if(flag){
for(BigInteger x=*this;x!=0;x=x.div2()){
res.emplace_back(x.digits[1]&1);
}
res.emplace_back(0);
reverse(res.begin(),res.end());
return res;
}else{
for(BigInteger x=-*this-1;x!=0;x=x.div2()){
res.emplace_back(!(x.digits[1]&1));
}
res.emplace_back(1);
reverse(res.begin(),res.end());
return res;
}
};
BigInteger::operator __int128()const{
__int128 res=0;
for(int i=size;i>=1;i--){
res=res*BASE+digits[i];
}
return res;
}
bool BigInteger::operator==(const BigInteger& x)const{
return !compare(x);
}
bool BigInteger::operator!=(const BigInteger& x)const{
return compare(x);
}
bool BigInteger::operator>=(const BigInteger& x)const{
return compare(x)>=0;
}
bool BigInteger::operator<=(const BigInteger& x)const{
return compare(x)<=0;
}
bool BigInteger::operator>(const BigInteger& x)const{
return compare(x)>0;
}
bool BigInteger::operator<(const BigInteger& x)const{
return compare(x)<0;
}
bool BigInteger::operator==(const long long& x)const{
return !compare(x);
}
bool BigInteger::operator!=(const long long& x)const{
return compare(x);
}
bool BigInteger::operator>=(const long long& x)const{
return compare(x)>=0;
}
bool BigInteger::operator<=(const long long& x)const{
return compare(x)<=0;
}
bool BigInteger::operator>(const long long& x)const{
return compare(x)>0;
}
bool BigInteger::operator<(const long long& x)const{
return compare(x)<0;
}
#if __cplusplus>201703L
auto BigInteger::operator<=> (const BigInteger& x)const{
return compare(x);
}
auto BigInteger::operator<=> (const long long& x)const{
return compare(x);
}
#endif
BigInteger BigInteger::operator+(const BigInteger& x)const{
if(!x.flag){
return *this-x.abs();
}
if(!flag){
return x-abs();
}
BigInteger res;
res.flag=1;
int n=std::max(size,x.size)+1;
res.reserve(n);
long long carry=0;
for(int i=1;i<=n;i++){
long long d1=i<=size?digits[i]:0,d2=i<=x.size?x.digits[i]:0;
res.push(d1+d2+carry);
carry=res.digits[i]/BASE;
res.digits[i]%=BASE;
}
while(res.size>1&&res.digits[res.size]==0){
res.pop();
}
return res;
}
BigInteger BigInteger::operator+(const long long& x)const{
if(x<0){
return *this-(-x);
}
if(!flag){
return -(abs()-x);
}
BigInteger res;
res.flag=1;
res.reserve(std::max(size,x==0?0:(int(log10(x))>>3)+1)+1);
long long carry=0,n=x;
for(int i=1;n||carry;i++){
res.push(n%BASE+(i<=size?digits[i]:0)+carry);
carry=res.digits[i]/BASE;
res.digits[i]%=BASE;
n/=BASE;
}
while(res.size>1&&res.digits[res.size]==0){
res.pop();
}
return res;
}
BigInteger BigInteger::operator-(const BigInteger& x)const{
if(!x.flag){
return *this+x.abs();
}
if(!flag){
return -(abs()+x);
}
BigInteger res;
if(*this<x){
res.flag=0;
}else{
res.flag=1;
}
long long carry=0;
int n=std::max(size,x.size);
res.reserve(n);
for(int i=1;i<=n;i++){
long long d1=i<=size?digits[i]:0,d2=i<=x.size?x.digits[i]:0;
res.push(d1-d2-carry);
if(res.digits[i]<0){
res.digits[i]+=BASE;
carry=1;
}else{
carry=0;
}
}
while(res.size>1&&res.digits[res.size]==0){
res.pop();
}
return res;
}
BigInteger BigInteger::operator-(const long long& x)const{
if(x<0){
return *this+(-x);
}
if(!flag){
return -(abs()+x);
}
BigInteger res;
res.flag=1;
res.reserve(std::max(size,(int(log10(x))>>3)+1));
long long carry=0,n=x;
for(int i=1;n||carry;i++){
res.push(n%BASE-digits[i]-carry);
if(res.digits[i]<0){
res.digits[i]+=BASE;
carry=1;
}else{
carry=0;
}
n/=BASE;
}
while(res.size>1&&res.digits[res.size]==0){
res.pop();
}
return res;
}
namespace FastFourierTransformation{
constexpr long long FFT_BASE=1e4;
constexpr double PI2=6.283185307179586231995927;
constexpr double PI6=18.84955592153875869598778;
constexpr int RECALC_WIDTH=10;
constexpr int RECALC_BASE=(1<<RECALC_WIDTH)-1;
struct complex{
double real,imag;
complex(double x=0.0,double y=0.0):real(x),imag(y){}
complex operator+(const complex&other)const{
return complex(real+other.real,imag+other.imag);
}
complex operator-(const complex&other)const{
return complex(real-other.real,imag-other.imag);
}
complex operator*(const complex&other)const{
return complex(real*other.real-imag*other.imag,real*other.imag+other.real*imag);
}
complex&operator+=(const complex&other){
return real+=other.real,imag+=other.imag,*this;
}
complex&operator-=(const complex&other){
return real-=other.real,imag-=other.imag,*this;
}
complex&operator*=(const complex&other){
return *this=*this*other;
}
};
complex *arr=nullptr;
inline void init(int n){
delete[] arr;
arr=new(std::nothrow)complex[n+1];
if(!arr){
throw std::bad_alloc();
}
}
template<const int n> inline void fft(complex*a){
const int n2=n>>1,n4=n>>2;
complex w(1.0,0.0),w3(1.0,0.0);
const complex wn(cos(PI2/n),sin(PI2/n)),wn3(cos(PI6/n),sin(PI6/n));
for(int i=0;i<n4;i++,w*=wn,w3*=wn3){
if(!(i&RECALC_BASE)){
w=complex(cos(PI2*i/n),sin(PI2*i/n)),w3=w*w*w;
}
complex x=a[i]-a[i+n2],y=a[i+n4]-a[i+n2+n4];
y=complex(y.imag,-y.real);
a[i]+=a[i+n2];
a[i+n4]+=a[i+n2+n4];
a[i+n2]=(x-y)*w;
a[i+n2+n4]=(x+y)*w3;
}
fft<n2>(a);
fft<n4>(a+n2);
fft<n4>(a+n2+n4);
}
template<> inline void fft<0>(complex*){}
template<> inline void fft<1>(complex*){}
template<> inline void fft<2>(complex*a){
complex x=a[0],y=a[1];
a[0]+=y;
a[1]=x-y;
}
template<> inline void fft<4>(complex*a){
complex a0=a[0],a1=a[1],a2=a[2],a3=a[3];
complex x=a0-a2,y=a1-a3;
y=complex(y.imag,-y.real);
a[0]+=a2;
a[1]+=a3;
a[2]=x-y;
a[3]=x+y;
fft<2>(a);
}
template<const int n> inline void ifft(complex*a){
const int n2=n>>1,n4=n>>2;
ifft<n2>(a);
ifft<n4>(a+n2);
ifft<n4>(a+n2+n4);
complex w(1.0,0.0),w3(1.0,0.0);
const complex wn(cos(PI2/n),-sin(PI2/n)),wn3(cos(PI6/n),-sin(PI6/n));
for(int i=0;i<n4;i++,w*=wn,w3*=wn3){
if(!(i&RECALC_BASE)){
w=complex(cos(PI2*i/n),-sin(PI2*i/n)),w3=w*w*w;
}
complex p=w*a[i+n2],q=w3*a[i+n2+n4];
complex x=a[i],y=p+q,x1=a[i+n4],y1=p-q;
y1=complex(y1.imag,-y1.real);
a[i]+=y;
a[i+n4]+=y1;
a[i+n2]=x-y;
a[i+n2+n4]=x1-y1;
}
}
template<> inline void ifft<0>(complex*){}
template<> inline void ifft<1>(complex*){}
template<> inline void ifft<2>(complex*a){
complex x=a[0],y=a[1];
a[0]+=y;
a[1]=x-y;
}
template<> inline void ifft<4>(complex*a){
ifft<2>(a);
complex p=a[2],q=a[3];
complex x=a[0],y=p+q,x1=a[1],y1=p-q;
y1=complex(y1.imag,-y1.real);
a[0]+=y;
a[1]+=y1;
a[2]=x-y;
a[3]=x1-y1;
}
inline void dft(complex*a,int n){
if(n<=1){
return;
}
switch(n){
case 1<<2:
fft<1<<2>(a);
break;
case 1<<3:
fft<1<<3>(a);
break;
case 1<<4:
fft<1<<4>(a);
break;
case 1<<5:
fft<1<<5>(a);
break;
case 1<<6:
fft<1<<6>(a);
break;
case 1<<7:
fft<1<<7>(a);
break;
case 1<<8:
fft<1<<8>(a);
break;
case 1<<9:
fft<1<<9>(a);
break;
case 1<<10:
fft<1<<10>(a);
break;
case 1<<11:
fft<1<<11>(a);
break;
case 1<<12:
fft<1<<12>(a);
break;
case 1<<13:
fft<1<<13>(a);
break;
case 1<<14:
fft<1<<14>(a);
break;
case 1<<15:
fft<1<<15>(a);
break;
case 1<<16:
fft<1<<16>(a);
break;
case 1<<17:
fft<1<<17>(a);
break;
case 1<<18:
fft<1<<18>(a);
break;
case 1<<19:
fft<1<<19>(a);
break;
case 1<<20:
fft<1<<20>(a);
break;
case 1<<21:
fft<1<<21>(a);
break;
case 1<<22:
fft<1<<22>(a);
break;
case 1<<23:
fft<1<<23>(a);
break;
case 1<<24:
fft<1<<24>(a);
break;
case 1<<25:
fft<1<<25>(a);
break;
case 1<<26:
fft<1<<26>(a);
break;
case 1<<27:
fft<1<<27>(a);
break;
case 1<<28:
fft<1<<28>(a);
break;
throw FFTLimitExceededError();
}
}
inline void idft(complex*a,int n){
if(n<=1){
return;
}
switch(n){
case 1<<2:
ifft<1<<2>(a);
break;
case 1<<3:
ifft<1<<3>(a);
break;
case 1<<4:
ifft<1<<4>(a);
break;
case 1<<5:
ifft<1<<5>(a);
break;
case 1<<6:
ifft<1<<6>(a);
break;
case 1<<7:
ifft<1<<7>(a);
break;
case 1<<8:
ifft<1<<8>(a);
break;
case 1<<9:
ifft<1<<9>(a);
break;
case 1<<10:
ifft<1<<10>(a);
break;
case 1<<11:
ifft<1<<11>(a);
break;
case 1<<12:
ifft<1<<12>(a);
break;
case 1<<13:
ifft<1<<13>(a);
break;
case 1<<14:
ifft<1<<14>(a);
break;
case 1<<15:
ifft<1<<15>(a);
break;
case 1<<16:
ifft<1<<16>(a);
break;
case 1<<17:
ifft<1<<17>(a);
break;
case 1<<18:
ifft<1<<18>(a);
break;
case 1<<19:
ifft<1<<19>(a);
break;
case 1<<20:
ifft<1<<20>(a);
break;
case 1<<21:
ifft<1<<21>(a);
break;
case 1<<22:
ifft<1<<22>(a);
break;
case 1<<23:
ifft<1<<23>(a);
break;
case 1<<24:
ifft<1<<24>(a);
break;
case 1<<25:
ifft<1<<25>(a);
break;
case 1<<26:
ifft<1<<26>(a);
break;
case 1<<27:
ifft<1<<27>(a);
break;
case 1<<28:
ifft<1<<28>(a);
break;
throw FFTLimitExceededError();
}
}
}
BigInteger BigInteger::fft_mul(const BigInteger& a,const BigInteger& b){
int least=(a.size+b.size)<<1,lim=1<<std::__lg(least);
if(lim<least){
lim<<=1;
}
FastFourierTransformation::init(lim);
for(int i=0;i<a.size;i++){
FastFourierTransformation::arr[i<<1].real=a.digits[i+1]%FastFourierTransformation::FFT_BASE;
FastFourierTransformation::arr[i<<1 |1].real=a.digits[i+1]/FastFourierTransformation::FFT_BASE%FastFourierTransformation::FFT_BASE;
}
for(int i=0;i<b.size;i++){
FastFourierTransformation::arr[i<<1].imag=b.digits[i+1]%FastFourierTransformation::FFT_BASE;
FastFourierTransformation::arr[i<<1 |1].imag=b.digits[i+1]/FastFourierTransformation::FFT_BASE%FastFourierTransformation::FFT_BASE;
}
dft(FastFourierTransformation::arr,lim);
for(int i=0;i<lim;i++){
FastFourierTransformation::arr[i]*=FastFourierTransformation::arr[i];
}
idft(FastFourierTransformation::arr,lim);
BigInteger res;
res.resize(a.size+b.size+1);
long long carry=0;
double inv=0.5/lim;
for(int i=0;i<=a.size+b.size;i++){
carry+=(long long)(FastFourierTransformation::arr[i<<1].imag*inv+0.5);
carry+=(long long)(FastFourierTransformation::arr[i<<1 |1].imag*inv+0.5)*FastFourierTransformation::FFT_BASE;
res.digits[i+1]+=carry%BASE;
carry/=BASE;
}
while(res.size>1&&res.digits[res.size]==0){
res.pop();
}
return res;
}
BigInteger BigInteger::operator*(const BigInteger& x)const{
BigInteger zero=0;
if(*this==zero||x==zero){
return zero;
}
int n=size,m=x.size;
long long lim=1LL*n*m;
if(lim>=FFT_LIMIT){
BigInteger res=fft_mul(*this,x);
res.flag=!(flag ^x.flag);
return res;
}
BigInteger res;
res.flag=!(flag ^x.flag);
res.resize(n+m+2);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
res.digits[i+j-1]+=digits[i]*x.digits[j];
res.digits[i+j]+=res.digits[i+j-1]/BASE;
res.digits[i+j-1]%=BASE;
}
}
for(int i=1;i<=n+m+1;i++){
res.digits[i+1]+=res.digits[i]/BASE;
res.digits[i]%=BASE;
}
while(res.size>1&&res.digits[res.size]==0){
res.pop();
}
return res;
}
BigInteger BigInteger::operator*(const long long& x)const{
BigInteger t=*this;
return t*=x;
}
BigInteger BigInteger::div2()const{
BigInteger res=*this;
for(int i=size;i>=1;i--){
if((res.digits[i]&1)&&(i>1)){
res.digits[i-1]+=BASE;
}
res.digits[i]>>=1;
}
while(res.size>1&&res.digits[res.size]==0){
res.pop();
}
return res;
}
BigInteger BigInteger::operator/(const long long& x)const{
if(x==0){
throw ZeroDivisionError();
}
if(*this==0){
return 0;
}
if(x==2){
return div2();
}
if(x==-2){
return-div2();
}
BigInteger res;
res.flag=!(flag ^(x>=0));
long long cur=0,div=std::abs(x);
res.resize(size);
for(int i=size;i>=1;i--){
cur=cur*BASE+digits[i];
res.digits[i]=res.flag?(cur/div):(-cur/-div);
cur%=div;
}
while(res.size>1&&res.digits[res.size]==0){
res.pop();
}
return res;
}
inline BigInteger BigInteger::_move_r(int d)const{
if(*this==0||d>=size){
return 0;
}
if(d==0){
return *this;
}
BigInteger res;
res.reserve(size-d+1);
for(int i=d+1;i<=size;i++){
res.push(digits[i]);
}
return res;
}
inline BigInteger BigInteger::_move_l(int d)const{
if(*this==0){
return 0;
}
if(d==0){
return *this;
}
BigInteger res;
res.reserve(size+d+1);
for(int i=1;i<=d;i++){
res.push(0);
}
for(int i=1;i<=size;i++){
res.push(digits[i]);
}
return res;
}
BigInteger BigInteger::newton_inv(int n)const{
if(*this==0){
throw ZeroDivisionError();
}
if(std::min(size,n-size)<=NEWTON_DIV_MIN_LEVEL){
BigInteger a;
a.resize(n+1);
memset(a.digits,0,sizeof(long long)*a.size);
a.digits[n+1]=1;
return a.divmod(*this,1).first;
}
int k=(n-size+2)>>1,k2=k>size?0:size-k;
BigInteger x=_move_r(k2);
int n2=k+x.size;
BigInteger y=x.newton_inv(n2),a=y+y,b=(*this)*y*y;
return a._move_l(n-n2-k2)-b._move_r(2*(n2+k2)-n)-1;
}
std::pair<BigInteger,BigInteger> BigInteger::newton_div(const BigInteger& x)const{
int k=size-x.size+2,k2=k>x.size?0:x.size-k;
BigInteger x2=x._move_r(k2);
if(k2!=0){
x2+=1;
}
int n2=k+x2.size;
BigInteger u=(*this)*x2.newton_inv(n2);
BigInteger q=u._move_r(n2+k2),r=(*this)-q*x;
while(r>=x){
q+=1;
r-=x;
}
return{q,r};
}
std::pair<BigInteger,BigInteger> BigInteger::divmod(const BigInteger& x,bool dis_newton)const{
static const int base=BigInteger::BASE;
BigInteger a=abs(),b=x.abs();
if(b==0){
throw ZeroDivisionError();
}
if(a<b){
return{0,flag?a:-a};
}
if(!dis_newton&&size>NEWTON_DIV_LIMIT){
return newton_div(x);
}
int t=base/(x.digits[x.size]+1);
a*=t;
b*=t;
int n=a.size,m=b.size;
BigInteger q=0,r=0;
q.resize(n);
for(int i=n;i>=1;i--){
r*=base,r+=a.digits[i];
long long d1=m<r.size?r.digits[m+1]:0,d2=m-1<r.size?r.digits[m]:0;
int d=(d1*base+d2)/b.digits[m];
r-=b*d;
while(!r.flag){
r+=b;
d--;
}
q.digits[i]=d;
}
q.flag=!(flag ^x.flag),r.flag=flag;
while(q.size>1&&q.digits[q.size]==0){
q.pop();
}
return{q,r/t};
}
BigInteger BigInteger::operator/(const BigInteger& x)const{
return divmod(x).first;
}
BigInteger BigInteger::operator%(const long long& x)const{
if(x==2||x==4||x==5){
return digits[1]%x;
}
return*this-(*this/x*x);
}
BigInteger BigInteger::operator%(const BigInteger& x)const{
return divmod(x).second;
}
BigInteger BigInteger::pow(const long long& x)const{
BigInteger res=1,a=*this;
for(long long t=x;t!=0;t>>=1){
if(t&1){
res=res*a;
}
a=a*a;
}
return res;
}
template<typename T> BigInteger BigInteger::pow(const long long& x,const T&p)const{
BigInteger res=1,a=*this%p;
for(long long t=x;t!=0;t>>=1){
if(t&1){
res=res*a%p;
}
a=a*a%p;
}
return res;
}
BigInteger BigInteger::root(const long long& m)const{
if(!flag&&m%2==0){
throw NegativeRadicandError();
}
if(m==1||*this==0){
return *this;
}
if(m==2){
return sqrt();
}
static constexpr long long base=BigInteger::BASE;
if(size<=m){
long long l=0,r=base-1;
while(l<r){
long long mid=(l+r+1)>>1;
if(BigInteger(mid).pow(m)<=*this){
l=mid;
}else{
r=mid-1;
}
}
return l;
}
if(size<=m*2){
BigInteger res;
res.resize(2);
long long l=0,r=base-1;
while(l<r){
long long mid=(l+r+1)>>1;
res.digits[2]=mid;
if(res.pow(m)<=*this){
l=mid;
}else{
r=mid-1;
}
}
res.digits[2]=l,l=0,r=base-1;
while(l<r){
long long mid=(l+r+1)>>1;
res.digits[1]=mid;
if(res.pow(m)<=*this){
l=mid;
}else{
r=mid-1;
}
}
return res.digits[1]=l,res;
}
int n=size,t=n/m/2;
BigInteger s=(_move_r(t*m).root(m)+1)._move_l(t);
BigInteger res=(s*(m-1)+*this/s.pow(m-1))/m;
long long l=std::max<long long>(res.digits[1]-100,0),r=std::min(res.digits[1]+100,base-1);
while(l<r){
long long mid=(l+r+1)>>1;
res.digits[1]=mid;
if(res.pow(m)<=*this){
l=mid;
}else{
r=mid-1;
}
}
return res.digits[1]=l,res;
}
BigInteger BigInteger::newton_invsqrt()const{
const BigInteger& x=*this;
static constexpr long long base=BigInteger::BASE;
if(x.size<=2){
if(x.size==0){
return 0;
}
uint64_t t=0;
if(x.size==1){
t=x.digits[1];
}else{
t=x.digits[1]+x.digits[2]*BASE;
}
return uint64_t(base*base/std::sqrt(t));
}
if(x.size<=NEWTON_SQRT_MIN_LEVEL){
BigInteger b1=BigInteger(base).pow(x.size/2);
return b1/x.sqrt_normal();
}
int n2=x.size%2==0?x.size:x.size+1,k2=(n2+2)/4*2;
BigInteger x2k(x.digits+1+(n2-k2),k2+x.size-n2);
BigInteger s=x2k.newton_invsqrt()._move_l((n2-k2)/2);
BigInteger x2=(s*3).div2()-(s*s*s*x).div2()._move_r(2*n2);
BigInteger rx=BigInteger(1)._move_l(2*n2)-x*x2*x2,delta=1;
if(!rx.flag){
for(;!rx.flag;delta*=2){
BigInteger t=(x2*2-delta+delta*delta)*x;
x2-=delta;
rx+=t;
}
}else{
while(1){
BigInteger t=(x2*2+delta)*delta*x;
if(t>rx){
break;
}
x2+=delta;
rx-=t;
delta*=2;
}
}
for(;delta>0;delta=delta.div2()){
BigInteger t=(x2*2+delta)*delta*x;
if(t<=rx){
x2+=delta;
rx-=t;
}
}
return x2;
}
BigInteger BigInteger::sqrt_normal()const{
static constexpr long long base=BigInteger::BASE;
BigInteger n=*this,x0=BigInteger(base)._move_l((n.size+2)>>1);
BigInteger x=(x0+n/x0).div2();
while(x<x0){
std::swap(x,x0);
x=(x0+n/x0).div2();
}
return x0;
}
BigInteger BigInteger::sqrt()const{
if(!flag){
throw NegativeRadicandError();
}
if(*this<=1){
return *this;
}
if(size<=NEWTON_SQRT_LIMIT){
return sqrt_normal();
}
const BigInteger& x=*this;
int n2=x.size%2==0?x.size:x.size+1;
BigInteger res=(x*x.newton_invsqrt())._move_r(n2);
BigInteger r=x-res*res,delta=1;
while(1){
BigInteger dr=(res*2+delta)*delta;
if(dr>r){
break;
}
r-=dr;
res+=delta;
delta*=2;
}
for(;delta>0;delta=delta.div2()){
BigInteger dr=(res*2+delta)*delta;
if(dr<=r){
r-=dr,res+=delta;
}
}
return res;
}
BigInteger BigInteger::gcd(const BigInteger& x)const{
BigInteger a=*this,b=x;
if(a<b){
std::swap(a,b);
}
if(b==0){
return a;
}
int t=0;
while(a%2==0&&b%2==0){
a=a.div2(),b=b.div2(),t++;
}
while(b>0){
if(a%2==0){
a=a.div2();
}else if(b%2==0){
b=b.div2();
}else{
a-=b;
}
if(a<b){
std::swap(a,b);
}
}
while(t--){
a+=a;
}
return a;
}
BigInteger BigInteger::lcm(const BigInteger& x)const{
return*this/gcd(x)*x;
}
BigInteger& BigInteger::operator+=(const long long& x){
return *this=*this+x;
}
BigInteger& BigInteger::operator+=(const BigInteger& x){
return *this=*this+x;
}
BigInteger& BigInteger::operator-=(const long long& x){
return *this=*this-x;
}
BigInteger& BigInteger::operator-=(const BigInteger& x){
return *this=*this-x;
}
BigInteger& BigInteger::operator*=(long long x){
if(x==0||*this==0){
return *this=0ll;
}
if(x<0){
flag=!flag,x=-x;
}
long long carry=0;
for(int i=1;i<=size||carry;i++){
if(i>size){
push(0);
}
long long cur=digits[i]*x+carry;
carry=cur/BigInteger::BASE;
digits[i]=cur%BigInteger::BASE;
}
while(size>1&&digits[size]==0){
pop();
}
return *this;
}
BigInteger& BigInteger::operator*=(const BigInteger& x){
return *this=*this*x;
}
BigInteger& BigInteger::operator/=(const long long& x){
return *this=*this/x;
}
BigInteger& BigInteger::operator/=(const BigInteger& x){
return *this=*this/x;
}
BigInteger& BigInteger::operator%=(const long long& x){
return *this=*this%x;
}
BigInteger& BigInteger::operator%=(const BigInteger& x){
return *this=*this%x;
}
BigInteger BigInteger::operator<<(const long long& x){
return *this*BigInteger(2).pow(x);
}
BigInteger BigInteger::operator>>(const long long& x){
return *this/BigInteger(2).pow(x);
}
BigInteger& BigInteger::operator<<=(const long long& x){
return *this=*this<<x;
}
BigInteger& BigInteger::operator>>=(const long long& x){
return *this=*this>>x;
}
BigInteger BigInteger::operator&(const BigInteger& x){
std::vector<bool> a=to_binary(),b=x.to_binary();
int n=a.size(),m=b.size(),lim=std::max(n,m);
std::vector<bool> res(lim),temp(lim);
if(m==lim){
a.resize(lim);
for(int i=0;i<n;++i){
temp[lim-n+i]=a[i];
}
a=temp;
}else{
b.resize(lim);
for(int i=0;i<m;++i){
temp[lim-m+i]=b[i];
}
b=temp;
}
for(int i=0;i<lim;++i){
res[i]=a[i]&b[i];
}
return res;
}
BigInteger BigInteger::operator|(const BigInteger& x){
std::vector<bool> a=to_binary(),b=x.to_binary();
int n=a.size(),m=b.size(),lim=std::max(n,m);
std::vector<bool> res(lim),temp(lim);
if(m==lim){
a.resize(lim);
for(int i=0;i<n;++i){
temp[lim-n+i]=a[i];
}
a=temp;
}else{
b.resize(lim);
for(int i=0;i<m;++i){
temp[lim-m+i]=b[i];
}
b=temp;
}
for(int i=0;i<lim;++i){
res[i]=a[i] |b[i];
}
return res;
}
BigInteger BigInteger::operator^(const BigInteger& x){
std::vector<bool> a=to_binary(),b=x.to_binary();
int n=a.size(),m=b.size(),lim=std::max(n,m);
std::vector<bool> res(lim),temp(lim);
if(m==lim){
a.resize(lim);
for(int i=0;i<n;++i){
temp[lim-n+i]=a[i];
}
a=temp;
}else{
b.resize(lim);
for(int i=0;i<m;++i){
temp[lim-m+i]=b[i];
}
b=temp;
}
for(int i=0;i<lim;++i){
res[i]=a[i] ^b[i];
}
return res;
}
BigInteger& BigInteger::operator&=(const BigInteger& x){
return *this=*this&x;
}
BigInteger& BigInteger::operator|=(const BigInteger& x){
return *this=*this|x;
}
BigInteger& BigInteger::operator^=(const BigInteger& x){
return *this=*this^x;
}
BigInteger& BigInteger::operator++(){
return *this+=1;
}
BigInteger BigInteger::operator++(int){
BigInteger t=*this;
return *this+=1,t;
}
BigInteger& BigInteger::operator--(){
return *this-=1;
}
BigInteger BigInteger::operator--(int){
BigInteger t=*this;return *this-=1,t;
}
BigInteger BigInteger::random(const int&num_digits){
std::random_device rd;
std::mt19937 gen(rd());
BigInteger res;
res.reserve(num_digits/8+8);
res.size=0;
std::uniform_int_distribution<long long> last_digits(1,std::pow(10,(num_digits-1)%8+1)-1);
if(num_digits%8){
res.push(last_digits(gen));
}
std::uniform_int_distribution<long long> other_digits(0,99999999);
for(int i=1;i<=num_digits/8;++i){
res.push(other_digits(gen));
}
return res;
}
```