爱悠闲 > 扩展欧几里得及组合数递推模板

扩展欧几里得及组合数递推模板

分类: 数学  |  标签: 扩展欧几里得,组合数递推  |  作者: whyorwhnt 相关  |  发布日期 : 2014-05-28  |  热度 : 607°

继续数学部分的学习,温故知新。

学习扩展欧几里得可以参考:

扩展欧几里得学习小记 - 将狼踩尽 19891101 - 博客园

欧几里得+扩展——数论总结2 - _%Corey的日志 - 网易博客

#define i64 __int64

i64 Extended_Euclid (i64 a,i64 b,i64 &x,i64 &y)
{//扩展欧几里得算法,求ax+by=gcd(a,b)的一组解(x,y),d=gcd(a,b)
    i64 d;
    if (b==0)
    {
        x=1;y=0;
        return a;
    }
    d=Extended_Euclid(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

组合数递推公式:

C(n, m)  = C(n -1, m - 1) + C(n - 1, m)

const int mod = 10007;
const int N = 1005;

int C[N][N];

void Init ()
{
	int i,j;
	for (i=1;i<=2000;i++)
	{
		C[i][0]=C[i][i]=1;
		for (j=1;j<i;j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	}
}