题目
一道算法题,用什么算法可以求解,
给出一个正n边形,顶点有编号1-n,要求画出k条对角线,这k条对角线在多边形内部没有交点(只可能相交在顶点处),问有多少种方法.输入多边形边数n和要画的对角线条数k.4
给出一个正n边形,顶点有编号1-n,要求画出k条对角线,这k条对角线在多边形内部没有交点(只可能相交在顶点处),问有多少种方法.输入多边形边数n和要画的对角线条数k.4
提问时间:2021-03-04
答案
#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));
}
#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
你是在英雄会上看到这个题目的吗?
大牛说这题很简单,可是费了我好大的力气才做出来
举一反三
已知函数f(x)=x,g(x)=alnx,a∈R.若曲线y=f(x)与曲线y=g(x)相交,且在交点处有相同的切线,求a的值和该切线方程.
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
奥巴马演讲不用看稿子.为什么中国领导演讲要看?
想找英语初三上学期的首字母填空练习……
英语翻译
最新试题
- 1一份特殊的礼物缩写150字以内不能超字数
- 25.12汶川地震后,甲乙两工程队奔赴四川支援灾区,其中甲是乙的2倍,后因工作需要,从甲工程队抽调16人去乙工程队,使得甲工程队比乙工程队的一半少3人,求甲乙原来多少人
- 3数轴上表示a和-2.5的两点P和Q之间的距离是10,求a
- 4This is the third time you _____(ask)me such a silly question
- 5高锰酸钾经加热后生成锰酸钾,二氧化碳和氧气..锰酸钾和二氧化碳都是固体物质.
- 6英语翻译:It means it is a warm day today.
- 7C公司只生产A产品,2011年产销60000件,每件售价500元.该产品单位变动成本占售价的80%,(.见下)
- 823、20、21、18、20、22、20、24的中位数是多少
- 9边长400米的正方形面积等于多少公顷
- 10油脂是高级脂肪酸的甘油脂怎么理解
热门考点
- 1(a+b+c)^2=a^2+b^2+c^2+2ab+2ac+abc式子解释
- 2小明.小亮.和小刚3个小朋友进行乒乓球比赛,小明比赛了5场,小亮比赛了4场,小刚比赛了3场,这三名小朋友
- 3初一英语;Add five new words to your vocab-Builder.中文怎样翻译?
- 4用两个长了cm、宽3cm、高1cm的长方体拼成一个大长方体,这个长方体的表面积最大是( ),最小是( )
- 5一条裤子原价180元,五一期间商场举行优惠活动,买三条送一条,妈妈买了三条裤子,比原来便宜多少钱?
- 6ttl 232
- 7银行利息一般保留几位小数?
- 8诲女知之乎,女读什么音
- 9一个养兔厂养白兔100只,黑兔是白兔的五分之三,灰兔是黑兔的四分之三,灰兔多少只?
- 10已知f(x)是奇函数,g(x)是偶函数,且f(x)+g(x)=sin@+cosx+3.求f(x)和g(x)的解析式.