用递推和组合数学时间复杂度是相同的（只使用高精度加法），而如果是一般的整数运算组合数学肯定快，O（1）。

其实所谓的dP 就是组合数学的递推公式，求得的结果和组合数学公式是相同的。用高精度算组合数学的也需要使用这个递推公式来保证只出现高精度加法，所以时间复杂度相同。

提醒一下后来人：

（1）高精度的DP一定要考虑动态数组，

1.减少内存的使用（我第一次直接开大数组用了50MB）

2.访问速度快。不要以为数组的访问时间不关痛痒，其实我就是栽在这上面了，当数组很大，维数较多时，访问一个数据是很慢的，尤其是高精度这个东西，需要频繁调用，所以我的总有一个点不断超时（虽然自己机器上测得不超，估计vijos将开数组的时间也计算在内了,而cena没有，为了谨慎。。）。

（2）同时高精度加法的数组开成byte就可以了，乘法要开成integer 否则可能溢出，这样的错误很难查出来，或者保证每次每位不超过9。

在内存允许的情况下开成integer较保险。

时间换来的教训，希望以后不要再栽倒这上面了。

一次ac

第180题，庆祝...

f[i][j]=f[j-1]+f[i][j-1];(j>1)

f[i][j]=f[0];(j=1)

f[i][0]=1(i>2)

f[i][0]=0(i0)

f[n][1...2^k-1]=1(w%k=0)

n=(w-1)%k

DP + 高精度(只需 add, sub) + 滚动数组

N = ( 1

这题就是一道组合题：

设m=2^k,z=2^(w mod k)-1

x=w div k

则ans=c(2,m-1)+c(3,m-1)+……+c(min(x,m-1),m-1)

若x

编译通过...

├ 测试数据 01：答案正确... 25ms

├ 测试数据 02：答案正确... 14ms

├ 测试数据 03：答案正确... 24ms

├ 测试数据 04：答案正确... 74ms

├ 测试数据 05：答案正确... 25ms

├ 测试数据 06：答案正确... 75ms

├ 测试数据 07：答案正确... 94ms

├ 测试数据 08：答案正确... 82ms

├ 测试数据 09：答案正确... 353ms

├ 测试数据 10：答案正确... 35ms

汗颜`\`\`\`\`\`\`\`

强烈BSING。。。。。。。。。。。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 41ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：41ms

这道题用三维足足调了两天还是不行，最后改成二维才只通过8个点，……最后

CHEAT了两个数据，真是对不起VIJOS了

五楼给的公式很有问题。

貌似：

q=2^k; n=min(w div k,q-2); m=w mod k;

ans=c(q-1,2)+c(q-1,3)+...+c(q-1,n+1)-c(q-2^m,n+1)

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

虽然因为一些小错误害得我检查了大半天才AC了，不过能0ms通过，还是挺有成就感的哦～～

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 25ms

├ 测试数据 09：答案正确... 338ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：363ms

的确恐怖！！！！

高精度不是很熟练

Accepted 有效得分：100 有效耗时：88ms

记录下``又一个不是0ms的

高精度太不熟练了 -___|-b

公式+高精……

高精有加法就足够了

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

终于知道NOIP时为什么这题才30 原来不是超时。。

杨辉+高精

noip题，建议大家用公式 + 高精度；

我的程序没超过60行（主要是要命的高精）。。。

解题报告没在，不能附解答过程了，

大概就这意思。

noip20分（没高精度强套公式的结果）。。。

用公式 + int64可以过8个点

楼下这位的高精度写的有点丑（应该只要乘法就够了）。。。

......

排列组合……只可惜我的高精……

沉思..........