jacky860226

#ifndef AVL_TREE
#define AVL_TREE
template<typename T>
class avl_tree{
	private:
		struct node{
			node *ch[2];
			int size;
			char h;
			T data;

jacky860226

#ifndef SUNMOON_FFT
#define SUNMOON_FFT
#include<vector>
#include<complex>
#include<algorithm>
template<typename T,typename VT=std::vector<std::complex<T> > >
struct FFT{
	const T pi;
	FFT(const T pi=acos((T)-1)):pi(pi){}
	inline unsigned int bit_reverse(unsigned int a,int len){

jacky860226

#ifndef SUNMOON_NTT
#define SUNMOON_NTT
#include<vector>
#include<algorithm>
template<typename T,typename VT=std::vector<T> >
struct NTT{
	const T P,G;
	NTT(T p=(1<<23)*7*17+1,T g=3):P(p),G(g){}
	inline unsigned int bit_reverse(unsigned int a,int len){
		a=((a&0x55555555U)<<1)|((a&0xAAAAAAAAU)>>1);

jacky860226

#include<functional>
#ifndef LEFTIST_TREE
#define LEFTIST_TREE
template<typename T,typename _Compare=std::less<T> >
class leftist_tree{
	private:
		struct node{
			T data;
			int deep;
			node *l,*r;

jacky860226

#ifndef SUNMOON_MIN_MAX_HEAP
#define SUNMOON_MIN_MAX_HEAP
#include<vector>
#include<algorithm>
template<typename T,typename _Seq=std::vector<T>,typename _Compare=std::less<T> >
class minmax_heap{
	_Seq s;
	_Compare cmp;
	bool is_min_level(size_t id){
		return !(std::__lg(++id)%2);

jacky860226

#include<functional>
#ifndef WEIGHT_BIASED_LEFTIST_TREE
#define WEIGHT_BIASED_LEFTIST_TREE
template<typename T,typename _Compare=std::less<T> >
class wb_leftist_tree{
	private:
		struct node{
			T data;
			int size;
			node *l,*r;

jacky860226

#include<functional>
#ifndef SKEW_HEAP
#define SKEW_HEAP
template<typename T,typename _Compare=std::less<T> >
class skew_heap{
	private:
		struct node{
			T data;
			node *l,*r;
			node(const T&d):data(d),l(0),r(0){}

jacky860226

inline int access(int x){
	int last=0;
	while(x){
		splay(x);
		node[x].ch[1]=last;
		up(x);
		last=x;
		x=node[x].pa;
	}
	return last;/*回傳access後splay tree的根*/

jacky860226

#ifndef CHINESE_REMAINDER_THEOREM
#define CHINESE_REMAINDER_THEOREM
template<typename T>
inline T Euler(T n){
	T ans=n;
	for(T i=2;i*i<=n;++i){
		if(n%i==0){
			ans=ans/i*(i-1);
			while(n%i==0)n/=i;
		}

jacky860226

using ull = unsigned long long;
ull _mod_mul(ull a,ull b,ull m){
	a%=m,b%=m;
	ull ans=0;
	for(;b;b>>=1){
		if(b&1){
			ans+=a;
			if(ans>=m)ans-=m;
		}
		a<<=1;