一道算法题,用什么算法可以求解,给出一个正n边形,顶点有编号1-n,要求画出k条对角线,这k条对角线在多边形内部没有交点（只可能相交在顶点处）,问有多少种方法.输入多边形边数n和要画的
更新时间：2024-04-25 21:03:37
1人问答
问题描述：
一道算法题,用什么算法可以求解,
给出一个正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("%dn",diagon(4, 1));
printf("%dn",diagon(5, 1));
printf("%dn",diagon(5, 2));
printf("%dn",diagon(6, 2));
printf("%dn",diagon(1000000000, 1000003));
}
运行结果：
2
5
5
21
999000
你是在英雄会上看到这个题目的吗?
大牛说这题很简单,可是费了我好大的力气才做出来
其它推荐
其它推荐
最新更新
精品分类
优秀其它推荐
热门其它
联系方式：