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

题目

一道算法题,用什么算法可以求解,
给出一个正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 ",diagon(4, 1));
printf("%d ",diagon(5, 1));
printf("%d ",diagon(5, 2));
printf("%d ",diagon(6, 2));
printf("%d ",diagon(1000000000, 1000003));
}

运行结果：

2

5

5

21

999000

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

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