首页 > 代码库 > 杨辉三角 x

杨辉三角 x

杨辉三角是美丽的数学结晶,其结论往往多蕴含自然之美.

                ——以下内容均摘抄自题解.

例题:

洛谷P1762  偶数

正如这题所示,数据在n<=10^15的范围内则引导我们去寻找空间更节省,速率更高效的算法。

首先,很明显,杨辉三角之特点在于其行数即等于每行的数字数。因此,可以很容易使用求和公式求出1到n行一共有多少个数字。

其次,通过观察,可以发现,奇数个数比偶数个数更有规律,其规律在于:

  1. 每行奇数个数一定为2^k(k为自然数)

  2. 当行数恰为2^k(k为自然数)时,奇数个数为2^k,偶数个数为零

  3. 当行数恰为2^k(k为自然数)时,奇数个数和恰为3^(k-1)

  4. 更巧妙的是:这个规律能更加扩展到一个不为2^k的数上,因为每一个数,都能分解为若干项2^k的和的形式。

举个例子吧:当n=2333;

2333= 2048+256+16+8+4+1

通过暴力程序,我们可以找出2333的所有奇数个数为190985

那么,我们找出如下数字

行数 所有奇数个数

2048 177147

256 6561

16 81

8 27 4 9 1 1

我们可以巧妙发现:177147 + 6561*2 + 81*4 + 27*8 + 9*16 + 1*32恰好等于190985!

那么,通过以上的探索,我们就能通过对n的分解,求出奇数总个数。

所以,偶数总个数也就不难得出了。

  1. 这样,我们就将一个看起来很困难的大量数求和,降级为极具规律性的数学公式求法。问题也顺理成章转化为如何将一个数分解为若干项2^k的和的形式。通过分析,我们知道算法的复杂度是O(logn)级的,足够通过所有的数据。

  2. 这道题目构思精巧,逻辑严密,能够告诉我们规律的寻找是一个漫长的探索过程,但是一旦得出了规律,世间万物自然水落石出!这个算法的正确性能够通过数学证明的,此处不赘述。

  3. 不要忘了膜题目要求的数字哦!

下面附探索规律的表格:

 

首先找规律什么的....(除了这个,其实也不一定对~~~~)

/*                                         前  前        前    前                                    每   i   i     每   i   i                                    排   排   排   排   排  排                                    偶   偶   偶   奇   奇   奇                                    数   数   数   数   数  数                                    个   个   和   个   个   和*/                  1                 0    0    0   1    1    1                 1 1                0    0    0   2    3    3                1 2 1               1    1    2   2    5    5               1 3 3 1              0    1    2   4    9    7              1 4 6 4 1             3    4    16  2    11    9            1 5 10 10 5 1           2    6    26  4    15   21          1 6 15 20 15 6 1          3    9    58  4    19    53        1 7 21 35 35 21 7 1         0    9    58  8    27  128      1 8 28 56 70 56 28 8 1        7    16   254  2    29  130    1 9 36 84 126 126 84 36 9 1     6    22   746  4    33  150         ......

大佬给出的:

// 行数 该行奇数 奇数和 偶数 偶数和   总数    1     1     1     0    0        1    2  (  2)    3     0    0        3    3  (  2)    5     1    1        6    4  (  4)    9     0    1        10    5  (  2)   11     3    4        15    6  (  4)   15     2    6        21    7  (  4)   19     3    9        28    8  (  8)   27     0    9        36    9  (  2)   29     7    16       45   10  (  4)   33     6    22       55   16  ( 16)   81     0    55       136   32  ( 32)  243     0    285      528   64  ( 64)  729     0    1351     2080  128  (128)  2187    0    6069     8256  256  (256)  6561    0    26335    32896  512  (512)  19683   0    111645   131328 1024 (1024)  59049   0    465751   524800 2048 (2048)  177147  0    1921029  2098176 4096 (4096)  531441  0    7859215  8390656

 

 

下面附探索规律的辅助程序:

#include <cstdio>using namespace std;int t, i, j, ou, line, e, tot;int mp[10005][10005];int judge(int x){    int v=1;    while (v<x)    {        v *=2;    }    if (v==x) return 1;    else return 0;}int main(){//  Input an integer in 10000!    scanf("%d",&e);    mp[1][1]=1;    ou = line = 0;    tot = 1;//行数(该行总数) 该行奇数 所有奇数 该行偶数 所有偶数 总数    printf("    1     1      1     0     0     1\n");    for (i=2; i<=e; ++i)    {        line=0;        for (j=1; j<=i; ++j)        {            mp[i][j]=mp[i-1][j-1]+mp[i-1][j];            if (mp[i][j]%2==0) ++line;        }        ou += line;        tot += i;        if (judge(i)==1)//保留该行可只查看N=2^k(k为自然数)的结果,若省略则查看所有结果         printf("%5d %5d %5d %5d %5d %5d\n", i, i-line, tot-ou, line, ou, tot);    }    return 0;}

附参考主程序:

#include <cstdio>#define mo 1000003using namespace std;long long n, d, z, ans, a[55], b[55], v, p;int i, t;int main(){    scanf("%lld",&v);    n = v;    z = 1;    d = z << 50; //因为2^50恰好大于10^15    t = 50;    while (n != 0)    {        if (n >= d)        {            n = n-d;            a[++a[0]] = t; //将2^t 的t存入数组中        }        d /= 2;        t--;    }    b[0] = 1;    for (i=1; i<=a[1]; ++i)        b[i]=(b[i-1]*3)%mo; //进行预处理,准备好3^t 的数字在数组b中    for (i=1; i<=a[0]; ++i)        ans += b[a[i]]*(long long)(z << i-1); //求所有奇数个数的和    p = (((z+v%mo)*(v%mo))/2); //求和公式    p %= mo;    ans %= mo;    if (p<ans) p += mo;    p = (p-ans)%mo; //总个数减去所有奇数个数就是偶数个数了    printf("%lld\n",p);    return 0;}

 

杨辉三角 x