现在的位置: 首页 > 综合 > 正文

2013.8.11-数学日2的总结

2018年02月21日 ⁄ 综合 ⁄ 共 1329字 ⁄ 字号 评论关闭

hoj 2761  给定一个类斐波那契数列,递推关系是a[n]=a[n-1]+2*a[n-2],a[0]=0,a[1]=3; 让求a[n]的位数。

忘记从哪里看来的方法了,貌似是某篇关于斐波那契数列求通项的,这里可以将a[n]=x^n,a[n-1]=x^(n-1),a[n-2]=x^(n-2)带进去,然后将x解出来,再利用a[0] a[1]的值就可以将a[n]的通项解出来了。。然后求位数,log10这个神器。最后注意加一

hoj 2628 也是关于斐波那契数列的,让求∑a[k]*a[n-k] (k>=0&&k<=n)..自己推了半天没发现有什么规律,于是乎各种找然后发现f[n]=(n*a[n+1]-a[n]-n*a[n-1])/5;没了。

hoj 2575 给定一个数n的2进制形式,然后让求满足2^k|n! 但是n!%2^(k+1)!=0的k,然后求出n-k;看样例yy了一下然后敲之居然过了。。随后就找 证明,发现用到了n!的素因子分解。不多解释了。

hoj 2843 求大组合数取模,p的范围是10e5,并且p是一个素数。这种情况下可以用lucas定理,也就是对于A B P且p为质数,那么A B就可以写成p进制,A=a[n]a[n-1]...a[0],B=b[n]b[n-1]...b[0]。则组合数C(A,B)与C(a[n],b[n])*C(a[n-1],b[n-1])*...*C(a[0],b[0])  mod p同余     即:Lucas(n,m,p)=C(n%p,m%p)*Lucas(n/p,m/p,p) 

hoj 2813 这个也是求大组合数的模,只不过在数据要求上不能保证p是素数,那么就要考虑其他方法。前几天学到的n!的素因子分解在这里可以用上了。C(n,m)=n!/m!/(n-m)!,可以分别将这三个数的阶乘分解素因子,然后每个素因子对应的个数相减,之后再乘起来就是结果、这个题当初做的时候WA好多次是因为取模的时候,每次应该ans=(ans%mod*------%mod)%mod; 

hoj 1076 farey序列的构造。

void make(int x1,int y1,int x2,int y2)
{
    if(x1+x2>n||y1+y2>n)return;
    make(x1,y1,x1+x2,y1+y2);
    tot++;
    printf("%d/%d\n",x1+x2,y1+y2);
    make(x1+x2,y1+y2,x2,y2);
}

hoj 1980 Catlan数 题意是在一个圆周上有2*n个点,在这些点之间两两连线,每个当且仅当与唯一的一个点相连,并且任意两条线段不相交。求这样的方案数。可以当做catlan数的又一个推广应用吧。

hoj 2282 求C(n,m)的因子个数,与2813类似。

hoj 2719 算是比较经典的组合数学题了。令m, n是非负整数且n >= m,有m+n个人站成一排要进入剧院,入场费为50元,这m+n个人中n个人有50元,m个人有100元,售票处开门时没有现金可以找零,问有多少种排队方式使得需要的时候总有零钱可以找?  这个可以转换为平面坐标上从一点出发到另一个点不经过对角线的方案数。

hoj 1778 Strling数%2  S(n,k)%2=((n-k)&(k-1)/2)==1;

【上篇】
【下篇】

抱歉!评论已关闭.