一道算法题,用什么算法可以求解,

问题描述：

一道算法题,用什么算法可以求解,
给出一个正n边形,顶点有编号1-n,要求画出k条对角线,这k条对角线在多边形内部没有交点（只可能相交在顶点处）,问有多少种方法.输入多边形边数n和要画的对角线条数k.4

答

#include <stdio.h>

#define P 1000003
#define LL long long
LL FACT[P+1];

// 初始化FACT数组,FACT[i]=i!%p
void InitFact(LL p) {
int i;
    FACT[0] = 1;
    for (i=1; i<=p; i++)
FACT[i] = (FACT[i-1] * i) % p;
}
// 返回 a^b%p
LL PowerMod(LL a, LL b, LL p)
{
LL ret = 1;
    LL tmp = a;
while (b)
{
        if (b & 1)
ret = (ret * tmp) % p;
        tmp = (tmp * tmp) % p;
        b >>= 1;
    }
    return ret;
}
// Lucas(n,m,p) = (Lucas(n/p,m/p) * C(n%p,m%p)) % p;
//*
// 返回 C(n,m)%p
LL C(LL n, LL m, LL p)
{
    if(n<m)
        return 0;
    return FACT[n] * PowerMod(FACT[m]*FACT[n-m]%p,p-2,p) % p;
}
LL Lucas(LL n, LL m, LL p)
{
    if(m==0)
        return 1;
    return (Lucas(n/p, m/p, p) * C(n%p, m%p , p))%p;
}
/*/
LL Lucas(LL n, LL m, LL p) {
    LL ret = 1;
LL nn, mm;
    while (n && m) {
        nn = n%p;
mm = m%p;
        if (nn < mm)
return 0;
        ret = (ret*FACT[nn] * PowerMod(FACT[mm]*FACT[nn-mm]%p, p-2, p) ) % p;
        n /= p;
        m /= p;
    }
    return ret;
}
//*/

int diagon (int n,int k)
{
LL result;
    InitFact(P);
    result = Lucas(n-3, k, P);
result = result*Lucas(n-1+k, k+1, P);
result = result * PowerMod((n-1)%P, P-2, P) %P;
return result;
}

intmain()
{
printf("%d\n",diagon(4, 1));
printf("%d\n",diagon(5, 1));
printf("%d\n",diagon(5, 2));
printf("%d\n",diagon(6, 2));
printf("%d\n",diagon(1000000000, 1000003));
}

运行结果：

999000

你是在英雄会上看到这个题目的吗?

大牛说这题很简单,可是费了我好大的力气才做出来

一道算法题,用什么算法可以求解,

相关推荐