首页 > 代码库 > 杨辉三角 x
杨辉三角 x
杨辉三角是美丽的数学结晶，其结论往往多蕴含自然之美.
——以下内容均摘抄自题解.
例题:
洛谷P1762 偶数
正如这题所示，数据在n<=10^15的范围内则引导我们去寻找空间更节省，速率更高效的算法。
首先，很明显，杨辉三角之特点在于其行数即等于每行的数字数。因此，可以很容易使用求和公式求出1到n行一共有多少个数字。
其次，通过观察，可以发现，奇数个数比偶数个数更有规律，其规律在于：
每行奇数个数一定为2^k（k为自然数）
当行数恰为2^k（k为自然数）时，奇数个数为2^k，偶数个数为零
当行数恰为2^k（k为自然数）时，奇数个数和恰为3^(k-1)
- 更巧妙的是：这个规律能更加扩展到一个不为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的分解，求出奇数总个数。
所以，偶数总个数也就不难得出了。
这样，我们就将一个看起来很困难的大量数求和，降级为极具规律性的数学公式求法。问题也顺理成章转化为如何将一个数分解为若干项2^k的和的形式。通过分析，我们知道算法的复杂度是O(logn)级的，足够通过所有的数据。
这道题目构思精巧，逻辑严密，能够告诉我们规律的寻找是一个漫长的探索过程，但是一旦得出了规律，世间万物自然水落石出！这个算法的正确性能够通过数学证明的，此处不赘述。
- 不要忘了膜题目要求的数字哦！
下面附探索规律的表格:
首先找规律什么的....(除了这个,其实也不一定对~~~~)
/* 前 前 前 前 每 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