一些常用算法模板

          之前做过acm，总结出来了一些算法模板。这些是我在搞懂先自己写然后想大牛靠拢不断优化的结果，可能有些是大牛们的源代码，在此一并发出，希望对大家有所帮助，代码中可能有错，在此表示歉意。

 动态规划模板
处理求矩阵的最大子矩
//************************************************************
//求a[n][m]的最大子矩阵
///计算从某固定行开始起连续列b[i,j]动态规划求最大值
int dp( const int *b,int m)
{
	int sum ,max,i;
	sum=max=b[0];
	for(i=1;i0)sum+=b[i];
		else sum=b[i];
		if(sum>max)max=sum;
	}
	return max;
}

//b[k]可以取到任意连续行的排列组合
max=-999999999;	
for(i=0;imax) max=dp(b,m);
	}
}
//************************************************************

动态规划求最大面积
//************************************************************
 {
  首先开辟数组a[N],l[N],r[N]
////找出其左右区间比其大的区间长度
        l[1]=1;  
        r[n]=n;  
       for (i=2; i<=n; ++i)  
        {  
           t=i;  
            while (t>1 && a[i]<=a[t-1]) t=l[t-1];  
            l[i]=t;  
        }  
        for (i=n-1; i>=1; --i)  
       {  
            t=i;  
            while (tmax) max=(r[i]-l[i]+1)*a[i];  
       } 
}
//************************************************************

最长公共子序列
//*********************************************************
//算法1:时间复杂度为O(N*M),空间复杂度为O(N*N)
const int MAXN=1000;
char str1[MAXN],str2[MAXN];
int dp[MAXN][MAXN];

int LCS1(char *str1,char *str2)
{
	int len1=strlen(str1);
	int len2=strlen(str2);
	int i,j;
	memset(dp,0,sizeof(dp));
	for(i=1;i<=len1;i++)
	{
		for(j=1;j<=len2;j++)
		{
			if(str1[i-1]==str2[j-1])
				dp[i][j]=dp[i-1][j-1]+1;
			else if(dp[i-1][j]>dp[i][j-1])
				dp[i][j]=dp[i-1][j];
			else dp[i][j]=dp[i][j-1];
		}
	}
	return dp[len1][len2];
}

//===============================================//算法2:时间复杂度为O(N*M),空间复杂度为O(N)
const int MAXN=1000;
char str1[MAXN],str2[MAXN];
int dp[2][MAXN];//采用滚动数组优化

int LCS2(char *str1,char *str2)
{
	int len1=strlen(str1);
	int len2=strlen(str2);
	int i,j,k;
	memset(dp,0,sizeof(dp));
	for(i=1;i<=len1;i++)
	{
		k=i&1;
		for(j=1;j<=len2;j++)
		{
			if(str1[i-1]==str2[j-1])
				dp[k][j]=dp[k][j-1]+1;
			else if(dp[k^1][j]>dp[k][j-1])
				dp[k][j]=dp[k^1][j];
			else dp[k][j]=dp[k][j-1];
		}
	}
	return dp[k][len2];
}
//*********************************************************

最长公共递增子序列
//************************************************************
 //其中a[n],b[n]分别存放俩序列
    memset(dp,0,sizeof(dp));
	max=0;
	for(i=0;ib[j]&&dp[k]>data[i][j];
		}
	}
	for(j=1;j<=m;j++)
		dp[n][j]=data[n][j];
	for(i=n-1;i>=1;i--)
	{
		for(j=i;j>=1;j--)
		{
			dp[i][j]=max(dp[i+1][j]+data[i][j],dp[i+1][j+1]+data[i][j]);
		}	
	}
}
//************************************************************

最长递增子序列
//求严格递增子序列的最长长度
//************************************************************
//算法1的时间复杂度为O(N*log(N))
const int MAXN=1000;
int data[MAXN];//存放原始数据
int MaxV[MAXN];//MaxV[i]存放长度为i的严格递增子序列的最大值的最小值

//二分查找返回MaxV中大于等于x的组靠左的下标
int BinaryResearch(int x,int len)
{
	int mid,low=1,high=len;
	while(low<=high)
	{
		mid=(low+high)>>1;
		if(MaxV[mid]MaxV[len])//比长度为len的子序列最大值大,直接加进末尾
			MaxV[++len]=data[i];
		else 
		{
			int pos=BinaryResearch(data[i],len);
			MaxV[pos]=data[i];
		}
	}
	return len;
}
//===============================================
//算法2的时间复杂度为O(N*N)
int dp[MAXN];
//返回原序列中严格递增子序列的最长长度
int LIS1(int n)
{
	int i,j,lmax;
	lmax=0;
	for(i=0;idata[j]&&dp[j]+1>dp[i])
				dp[i]=dp[j]+1;
		}
		if(dp[i]>lmax)lmax=dp[i];
	}
	return lmax;
}
//************************************************************

最大字段和
//************************************************************
void MSS(int n)
{
	int i;
	int max=NINF;
	memset(dp,0,sizeof(dp));
	for(i=1;i<=n;i++)
	{
		if(dp[i-1]<=0)
			dp[i]=data[i];
		else dp[i]=dp[i-1]+data[i];
		if(max=weight;i--)
		dp[i]=max(dp[i],dp[i-weight]+value);
}
void CompletePack(int weight,int value,int lim)
//对应完全背包的求法
{
    for(int i=weight;i<=lim;i++)
		dp[i]=max(dp[i],dp[i-weight]+value);
}
void MultiplePack(int weight,int value,int amount,int lim)
//选定物品后的多重背包的求法
{
    if(weight*amount>=lim)CompletePack(weight,value,lim);
    else
    {
        for(int k=1;k=da[i])//保证inc队列在start-i区间内的递增
			rear2--;
		Inc[++rear2]=i;
		while(da[Dec[front1]]-da[Inc[front2]]>k)
		{
			//保证区间左端点向后滑动一个长度
			if(Dec[front1]-Inc[front2]<0)
			{
				start=Dec[front1]+1;
				front1++;
			}
			else
			{
				start=Inc[front2]+1;
				front2++;
			}
		}
		//满足m<=Max-Min<=k
		if(da[Dec[front1]]-da[Inc[front2]]>=m)
		{
			if(i-start+1>ans)
				ans=i-start+1;
		}
	}
	return ans;
}

并查集
//*****************************************************************
1.求父亲节点并压缩路径
int par[MAX];
int Get_par(int a)
//查找a的父亲节点并压缩路径
{
	if(par[a]==a)
		return par[a];
	//注意语句的顺序
	int pa=par[a];
	par[a]=Get_par(par[a]);
//
	return par[a];
}

2.合并
void Merge(int a,int b)
//合并a,b
{
	int pa,pb;
	pa=Get_par(a);
	pb=Get_par(b);
	par[pa]=pb;
}
//*****************************************************************

线段树
不带延迟更新的操作
//************************************************************
int da[MAXN];
struct node 
{
	int left,right,sum;//sum此处灵活处理
}tree[MAXN*4];
//1.建立以left,right为左右边界,将数组da中元素存储在首地址从1开始的线段树tree的叶节点上
void Build( int id,int left,int right)
{
    tree[id].left=left;
    tree[id].right=right;
    if(left==right)
    {
		//tree[id].sum=da[left];//此处可以直接初始化为对应da[left]
		return ;
    }
    else
    {
		int mid =(left+right)>>1;        
        Build(id<<1,left,mid);
        Build((id<<1)|1,mid+1,right);
		//tree[id].sum=tree[(id<<1)].sum+tree[(id<<1)|1].sum;
   }
}

//2.在线段树的叶节点pos处加val
void Updata(int id,int pos,int val)
{
    tree[id].sum+=val;
    if(tree[id].left==tree[id].right&&tree[id].left==pos)
    {
        return ;
    }
    int mid=(tree[id].left+tree[id].right)>>1;
    if(pos<=mid) 
        Updata(id<<1,pos,val);
    else 
        Updata((id<<1)|1,pos,val);
}

//3.查询区间[left,right]上的和
int Query(int id,int left,int right)
{
    if(tree[id].left==left&&tree[id].right==right)
    {
        return tree[id].sum;
    }
    int mid=(tree[id].left+tree[id].right)>>1;
    if(right<=mid)
        return Query(id<<1,left,right);
    if(left>=mid+1)
        return Query((id<<1)|1,left,right);
    return Query(id<<1,left,mid)+Query((id<<1)|1,mid+1,right);
}
//************************************************************

线段树的延迟更新
//*****************************************************
const int MAXN=100000+100;
struct node 
{
	int left,right,add;
	int Max;
}tree[MAXN*4];

void build(int id, int left, int right)
{
	tree[id].add=0;
	tree[id].left=left;
	tree[id].right=right;
	tree[id].Max=0;
	if(left==right)
	{
		return ;
	}
	else
	{
		int mid=(left+right)>>1;        
		build(id<<1,left,mid);
		build((id<<1)|1,mid+1,right);
	}
}

void updata(int id,int left,int right,int adi)
{
	if(tree[id].left==left&&tree[id].right==right)
	{
		tree[id].add+=adi;
		return ;
	}
	int mid=(tree[id].left+tree[id].right)>>1;
	if(right<=mid)
		updata(id<<1,left,right,adi);
	else if(left>mid)
		updata((id<<1)|1,left,right,adi);
	else
	{
		updata(id<<1,left,mid,adi);
		updata((id<<1)|1,mid+1,right,adi);
	}
	tree[id].Max=max(tree[id<<1].Max+tree[id<<1].add,tree[(id<<1)|1].Max+tree[(id<<1)|1].add);
}

int query(int id,int left,int right)
{
	if(tree[id].left==left&&tree[id].right==right)
	{
		return tree[id].Max+tree[id].add;
	}
	int mid=(tree[id].left+tree[id].right)>>1;
	if(tree[id].add!=0)
	{
		updata(id<<1,tree[id].left,mid,tree[id].add);
		updata((id<<1)|1,mid+1,tree[id].right,tree[id].add);
		tree[id].Max=max(tree[id<<1].Max+tree[id<<1].add,tree[(id<<1)|1].Max+tree[(id<<1)|1].add);
		tree[id].add=0;
	}
	if(right<=mid)
		return query(id<<1,left,right);
	else if(left>mid )
		return query((id<<1)|1,left,right);
	else 
	{
		return max(query(id<<1,left,mid),query((id<<1)|1,mid+1,right));
	}
}
//*****************************************************************

RMQ问题的ST算法
//*****************************************************************
const int MAXN=50000+100;
const int Mpow=16;//保证2^(Mpow)>MAXN即可
int data[MAXN];
int Maxdp[MAXN][Mpow];
int Mindp[MAXN][Mpow];
inline int Min(int a,int b)
{
	return ab?a:b;
}
inline void init(int n)
{
	for(int i=1;i<=n;i++)
	{
		Mindp[i][0]=Maxdp[i][0]=data[i];
	}
}
//预处理过程，时间复杂度为O(N*log(N))
//ST算法求区间最值
//dp[i][j]表示区间[i,i+2^j-1]最值
//求dp[i][j]时将其分成dp[i][j-1],dp[i+2^(j-1)][j-1]
//[i,i+2^j-1]=[i,i+2^(j-1)-1]+[i+2^(j-1),i+2^(j-1)+2^(j-1)-1]
inline void Rmp_ST(int n)
{
	int l,s;
	for(l=1;l<=16;l++)
	{
		for(s=1;s<=n;s++)
		{
			if(s+(1<0) 
   {  
      nSum+=C[p]; 
      p-=Lowbit[p]; 
   } 
    return nSum; 
} 

//2.修改+初始化
void Modify(int p,int val) 
//原数组中下表为p的元素+val，导致C[]数组中部分元素值的改变
{ 
    while(p<=MAXN-10) 
   { 
      C[p]+=val; 
      p+=Lowbit[p]; 
    } 
} 
//************************************************************

二维树状数组
//*****************************************************************
1.修改
void Add( int y, int x,int a)
//原数组中下表为[y][x]的元素+a，导致C[][]数组中部分元素值的改变
{
	while( y <= s )
	{ 
		int tmpx = x;
		while( tmpx <= s )
		{
			C[y][tmpx] += a;
			tmpx += Lowbit[tmpx];
		}
		y += Lowbit[y];
	}
}
2.查询
int QuerySum( int y, int x)
//查询第1行到第y行，第1列到第x列的和
{
	int nSum = 0;
	while( y > 0 ) 
	{
		int tmpx = x;
		while( tmpx > 0) 
		{
			nSum += C[y][tmpx];
			tmpx -= Lowbit[tmpx];
		}
		y -= Lowbit[y];
	}
	return nSum;
}
//*****************************************************************

划分树
//*****************************************************************
const int MAXN=100010;
int tree[30][MAXN];//表示每层每个位置的值
int sorted[MAXN];//已经排序的数
int toleft[30][MAXN];//toleft[p][i]表示第p层从1到i有多少个数分入左边

//创建划分树
//时间复杂度为O(N*log(N))
void build(int l,int r,int dep)
{
	int i;
    if(l==r)return;
    int mid=(l+r)>>1;
    int same=mid-l+1;//表示等于中间值而且被分入左边的个数
    for(i=l;i<=r;i++)
      if(tree[dep][i]0)
        {
            tree[dep+1][lpos++]=tree[dep][i];
            same--;
        }
        else  //比中间值大分入右边
            tree[dep+1][rpos++]=tree[dep][i];
        toleft[dep][i]=toleft[dep][l-1]+lpos-l;//从1到i放左边的个数

    }
    build(l,mid,dep+1);
    build(mid+1,r,dep+1);
}

//查询区间第k小的数，[L,R]是大区间，[l,r]是要查询的小区间
//时间复杂度为O(log(N))
int query(int L,int R,int l,int r,int dep,int k)
{
    if(l==r)return tree[dep][l];
    int mid=(L+R)>>1;
    int cnt=toleft[dep][r]-toleft[dep][l-1];//[l,r]中位于左边的个数
    if(cnt>=k)
    {
        //L+要查询的区间前被放在左边的个数
        int newl=L+toleft[dep][l-1]-toleft[dep][L-1];
        //左端点加上查询区间会被放在左边的个数
        int newr=newl+cnt-1;
        return query(L,mid,newl,newr,dep+1,k);
    }
    else
    {
         int newr=r+toleft[dep][R]-toleft[dep][r];
         int newl=newr-(r-l-cnt);
         return query(mid+1,R,newl,newr,dep+1,k-cnt);
    }
}
Init()
{
     memset(toleft,0,sizeof(toleft));  
     for(i=1;i<=n;i++)  
     { 
        scanf("%d",&tree[0][i]); 
         sorted[i]=tree[0][i]; 
     } 
      sort(sorted+1,sorted+n+1);  
      build(1,n,0); 
}
//*****************************************************************

字符串匹配
Manacher算法求最长回文子串
//*****************************************************************
const int MAXN=1000000+100;
char str1[MAXN*2],str2[MAXN*2];//待处理字符串
int num[MAXN*2];
//将str1变成str2,如abab变成$#a#b#a#b#
void init()
{
	int i,id;
	str2[0]='$';
	str2[1]='#';
	for(i=0,id=2;str1[i];i++,id+=2)
	{
		str2[id]=str1[i];
		str2[id+1]='#';
	}
	str2[id]=0;
}
//Manacher算法求最长回文子串,时间复杂度为O(N)
int Manacher()
{
	int i,ans=0,MxR=0,pos=1;
	for(i=1;str2[i];i++)
	{
		if(MxR>i)num[i]=num[pos*2-i]<(MxR-i)?num[pos*2-i]:(MxR-i);
		else num[i]=1;
		while(str2[i+num[i]]==str2[i-num[i]])
			num[i]++;
		if(num[i]+i>MxR)
		{
			MxR=num[i]+i;
			pos=i;
		}
		if(ans0&&T[i]!=W[j])
          j=next[j];
        if(W[j]==T[i])j++;
        if(j==wlen)
        {
            ans++;
            j=next[j];
        }
    }
    return ans;
}
//返回模式串T在主串S中首次出现的位置
//返回的位置是从0开始的,若没有找到返回-1。
int KMP_Index(char *W,char *T)
{
    int i=0, j=0,wlen=strlen(W),tlen=strlen(T);
    getNext(W);
    while(istr[(j+k)%len])
			i=i+k+1;
		    else 
			j=j+k+1;
			if(i==j)j++;
			k=0;
		}
	}
	return ++i<++j?i:j;
}
//*****************************************************************

字典树
//************************************************************
//定义字典树结构体
struct Trie
{
	Trie* next[26];
	int flag;
};
Trie *root;
//初始化root
void init()
{
	root=new Trie;
	memset(root,0,sizeof(Trie));
}
//2.插入
//将str插入以root为根节点的字典树中
void insert(char *str)
{
    int len = strlen(str);
    Trie *s = root;
    for (int i = 0; i next[str[i] - 'a'])
            s = s->next[str[i] - 'a'];
        else
		{
            Trie* t = new Trie;
            memset(t, 0, sizeof (Trie));
            s->next[str[i] - 'a'] = t;
            s = t;
        }
	}
	s->flag = 1;
}
//3.查找
//查找字典树中是否有元素str
int find(char *str)
{
    int len = strlen(str);
    Trie *s = root;
    for (int i = 0; i next[str[i] - 'a'])
            s = s->next[str[i] - 'a'];
        else
            return 0;
	}
	return s->flag;/////////////////////flag可能不标志为单词结尾
}
//5.释放内存空间
//释放以root为根节点的字典树内存空间
void del(Trie *root)
{
    Trie *s = root;
    for (int i = 0; i <26; i++)
	{
        if (s->next[i])
            del(s->next[i]);
    }
    delete s;
    s = NULL;
}
//*****************************************************************

AC自动机模板
//************************************************************
const int kind = 26;//视具体情况改动
struct node
{
	node *fail; //失败指针
	node *next[kind]; //Tire每个节点的26个子节点（最多26个字母）
	int count; //是否为该单词的最后一个节点
	node()
	{ //构造函数初始化
		fail=NULL;
		count=0;
		memset(next,NULL,sizeof(next));
	}
}*q[1000*255]; //队列方便用于bfs构造失败指针，大小应依据Tries图//节点个数而定
int head,tail; //队列的头尾指针
node *Root;
//1.建立Tries
void insert(char *str,node *root)
//建立一颗以root为根节点的不带前缀指针的字典树
{
	node *p=root;
	int i=0,index;
	while(str[i])
	{
		index=str[i]-'A';//视具体情况改动
		if(p->next[index]==NULL) 
			p->next[index]=new node();
		p=p->next[index];
		i++;
	}
	p->count=1;
}
//2.建立前缀指针，形成Tries图
void build_ac_automation(node *root)
//在建好的字典树上添加前缀指针，形成Tries图，即ac自动机
{
	int i;
	root->fail=NULL;
	q[head++]=root;
	while(head!=tail)
	{
		node *temp=q[tail++];
		node *p=NULL;
		for(i=0;inext[i]!=NULL)
			{
				if(temp==root) 
					temp->next[i]->fail=root;
				else
				{
					p=temp->fail;
					while(p!=NULL)
					{
						if(p->next[i]!=NULL)
						{
							temp->next[i]->fail=p->next[i];
							break;
						}
						p=p->fail;
					}
					if(p==NULL) 
						temp->next[i]->fail=root;
				}
				q[head++]=temp->next[i];
			}
		}
	}
}
//3.查询母串
int query(node *root,char *s)
//有多少种模式串出现在母串str[]中
{
	int i=0,cnt=0,index,len=strlen(s);
	node *p=root;
	while(s[i])
	{
		index=s[i]-'A';//视具体情况改动
		while(p->next[index]==NULL && p!=root)
			p=p->fail;
		p=p->next[index];
		p=(p==NULL)?root:p;
		node *temp=p;
		while(temp!=root&&temp->count)
		{
			cnt+=temp->count;
			temp->count=0;
			temp=temp->fail;
		}	
		i++;
	}
	return cnt;
}
//4.初始化
void init()
{
	head=tail=0;
	Root=new node;
}
//************************************************************

后缀数组
//*****************************************************************
const int MAXN=100000+100;
char str[MAXN];//待处理字符串
int sa[MAXN];//求得的后缀数组
int wa[MAXN],wb[MAXN],wv[MAXN],wh[MAXN];
int cmp(int *r,int a,int b,int l)
{
	return r[a]==r[b]&&r[a+l]==r[b+l];
}
//求后缀数组sa[],下标1到n-1(此处n=strlen(str)+1)有效后缀
//将str的n个后缀从小到大进行排序之后把排好序的后缀的开头位置顺次放入sa中。
//保证Suffix(sa[i])=0;i--) sa[--wh[x[i]]]=i;
	for(j=1,p=1;p=j) y[p++]=sa[i]-j;
		for(i=0;i=0;i--) sa[--wh[wv[i]]]=y[i];
		for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i=midlen)//长度大于等于midlen
			{
				lowid=min(lowid,sa[i]);
				highid=max(highid,sa[i]);
				if(highid-lowid>=midlen)//且不重叠
					flag=true;
			}
		}
		if(flag)Minlen=midlen+1;
		else Maxlen=midlen-1;
	}
	return Maxlen<4?0:Maxlen+1;
}
//*****************************************************************


             
                 4.图论
邻接表建图
//*****************************************************
const int MAXN=1000+100;
const int INF = 0x3f3f3f3f;

int head[MAXN];
int dis[MAXN];
bool visited[MAXN];
int qq[MAXN];//模拟队列
struct node
{
    int to;
    int next;
}Edg[20000+100];
int n,m,tot;

void init()
{
    tot=0;
    memset(head,-1,sizeof(head));
}

void add(int a,int b)
{
    Edg[tot].to=b;
    Edg[tot].next=head[a];
    head[a]=tot++;
}

void BFS(int s)
{
    //queueqq;
    //qq.push(s);
    int front,rear;
     frOnt=rear=0;     
    qq[front++]=s;
    int now,i,to;
    for(i=1;i<=n;i++)
    {
        if(i!=s)dis[i]=INF;
        else dis[i]=0;
    }
    visited[s]=true;
    while(rearj的有向边就可以了，是左边向右边的匹配
//g没有边相连则初始化为0
//uN是匹配左边的顶点数，vN是匹配右边的顶点数
//调用：res=hungary();输出最大匹配数
//优点：适用于稠密图，DFS找增广路，实现简洁易于理解
//时间复杂度:O(VE)
//************************************************************
//顶点编号从0开始的
const int MAXN=510;
int uN,vN;//u,v数目
int g[MAXN][MAXN];
int linker[MAXN];
bool visited[MAXN];
bool dfs(int u)//从左边开始找增广路径
{
    int v;
    for(v=0;vdis[j])
				temp=dis[k=j];
		if(temp==INF)break;
		visited[k]=1;
		for(j=1;j<=n;++j)
			if(!visited[j]&&dis[j]>dis[k]+g[k][j])
				dis[j]=dis[k]+g[k][j];
	}
}
//************************************************************

flyod算法
//*****************************************************************
int const Max=1001; 
int a[Max][Max];//存放边的权值
int b[Max];//存放顶点的权值
int nex[Max][Max]; //next[i][j]用来保存i-->j的最短路径中i的最优后即最近的顶点
int N; 
void floyd()
//flyod算法求个顶点间的最短路径长度并记录路径
{
	int i,j,k,fee; 
	
	for(i=1;i<=N;i++)
		for(j=1;j<=N;j++)
			nex[i][j]=j; 
		

		for(k=1;k<=N;k++)
		{
			for(i=1;i<=N;i++)
			{
				if(i==k||a[i][k]==-1)
					continue;
				for(j=1;j<=N;j++)
				{
					if(a[k][j]==-1||j==k)
						continue; 
					fee = a[i][k]+a[k][j]+b[k]; 
					if(a[i][j]==-1||a[i][j]>fee)
					{
						a[i][j]=fee; 
						nex[i][j]=nex[i][k]; 
					}
					//选择字典序小的路径
					else if(a[i][j]==fee)
					{
						if(nex[i][j]>nex[i][k])
							nex[i][j]=nex[i][k];
					}
				}
			}
		}
}

void path(int i, int j)
//递归输出最短路径
{
	if(j==nex[i][j])
	{
		printf("%d-->%d\n",i,j); 
	}
	else 
	{
		printf("%d-->",i); 
		path(nex[i][j],j);  
	}
}
//*****************************************************************



            数论
矩阵快速幂
//*****************************************************
//origin存放需计算的矩阵，res存放答案矩阵
//最终答案为res.a[1][0](对应f[n])
struct matrix
{
	__int64 a[2][2];
};
matrix origin,res;
//将res初始化为初始条件矩阵，人为输入关系递推矩阵origin
void init()
{
	origin.a[0][0]=1,origin.a[1][0]=origin.a[0][1]=1,origin.a[1][1]=0;
	res.a[0][0]=1,res.a[0][1]=res.a[1][0]=res.a[1][1]=0;
}
//直接将2个矩阵相乘x*y,返回计算后的矩阵
matrix multiply(matrix &x,matrix &y,__int64 MOD)
{
	matrix temp;
	memset(temp.a,0,sizeof(temp.a));
	for(int i=0;i<2;i++)
	{
		for(int j=0;j<2;j++)
		{
			for(int k=0;k<2;k++)
			{
				temp.a[i][j]+=x.a[i][k]*y.a[k][j];
				temp.a[i][j]%=MOD;
			}
		}
	}
	return temp;
}
//矩阵快速幂的计算,矩阵的n次幂，每个中间结果对MOD取模
void calc(matrix &origin,matrix &res,__int64 n,__int64 MOD)
{
	while(n)
	{
		if(n&1)
			res=multiply(origin,res,MOD);
		n>>=1;
		origin=multiply(origin,origin,MOD);
	}
}
//*****************************************************

快速幂
A^B %C=A^( B%phi(C)+phi(C) ) %C     B>=phi(C)
//************************************************************
//快速幂x^n%mod的计算
__int64 optimized_pow_n(__int64 x, __int64 n)
{
    __int64  pw = 1;
    while (n > 0)
	{
        if (n & 1)       
            pw *= x;
		 pw=pw%mod;
        x *= x;
		 x=x%mod;
        n >>= 1;     
    }
    return pw;
}
//************************************************************

三分法求凹凸函数的极值点
//*****************************************************
//当需要求某凸性或凹形函数的极值，通过函数本身表达式并不容易求解时，就可以用三分法不断逼近求解
double mid, midmid;
while ( low + eps  cmidmid ) 
		    high = midmid;
    else 
        low = mid;
}
//*****************************************************

普通母函数
//*****************************************************
//普通母函数,求组合数。
int n,sum;//n表示物品种类数，sum为在[1,sum]范围类求每个价值的组合数（不排列）
int num[100+10],value[100+10];//num[]存放该种类对应的个数,value[]存放该种类对应的价值
int a[10000+100];
int b[10000+100];
void Generating_function()
{
	int i,j,k;
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	a[0]=1;
	for(i=1;i<=n;i++)
	{
		for(j=0;j<=sum;j++)
		{
			for(k=0;k<=num[i]&&k*value[i]+j<=sum;k++)
			{
				b[k*value[i]+j]+=a[j];
				b[k*value[i]+j]%=10000;
			}
		}
		memcpy(a,b,sizeof(b));
		memset(b,0,sizeof(b));
	}
}
//*****************************************************

最大公约数
//*****************************************************
//求a,b的最大公约数
LL Gcd(LL a,LL b)
{
	return b==0?a:Gcd(b,a%b); 
} 
//*****************************************************












计算几何

//求不共线三点的外接圆，利用圆心到三点距离相等联立方程求得
point GetCentre(point a,point b,point c)
{
	double a1=b.x-a.x,b1=b.y-a.y,c1=(a1*a1+b1*b1)/2;
	double a2=c.x-a.x,b2=c.y-a.y,c2=(a2*a2+b2*b2)/2;
	double d=a1*b2-a2*b1;
	point ret;
	ret.x=a.x+(c1*b2-c2*b1)/d;
	ret.y=a.y+(a1*c2-a2*c1)/d;
	return ret;
}


头文件及宏定义
#include
#include
#include
#include
#include
#include
#include
#include
#include