-
#include
一些常用算法模板(四)
]; } //选择字典序小的路径 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 < high ) { mid = (low + high) / 2; midmid = (mid + high ) / 2; double cmid = cal(mid); double cmidmid = cal(midmid); if ( cmid > 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