HDU 4927 大数

本文主要是介绍HDU 4927 大数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意很简单：

对于长度为n的数，做n-1遍，生成的新数列： 

b1=a2-a1   b2=a3-a2  b3=a4-a3

c1=b2-b1   c2=b3-b2

ans=c2-c1

最后推出公式：  为n所在行的杨辉三角

对于样例：

3

1 2 3

ans=1*1-2*2+1*3=0

4

1 5 7 2

ans=-1*1+3*5-3*7+1*2=-5

求杨辉三角每个数的时候可以优化一下，后一个数由前一个各乘除一次就好了

JAVA用大数秒A。。。BUT 不会JAVA  - -#

蛋疼用C++模拟大数。。

#include "stdio.h"
#include "string.h"
int a[3010];
__int64 mark[3010],ans[3010],c[3010];
int Max(int a,int b)
{if (a<b) return b;else return a;
}void make_mul(int x)
{int i;for (i=1;i<=mark[0];i++)mark[i]*=x;for (i=1;i<=mark[0];i++){mark[i+1]+=mark[i]/1000000;mark[i]%=1000000;}while (mark[mark[0]+1]!=0){mark[0]++;mark[mark[0]+1]=mark[mark[0]]/1000000;mark[mark[0]]%=1000000;}}void make_div(int x)
{int i;for (i=mark[0];i>=2;i--){mark[i-1]+=(mark[i]%x)*1000000;mark[i]/=x;}mark[1]/=x;while (mark[mark[0]]==0) mark[0]--;
}void make_add()
{int i,op;if (ans[0]>0){for (i=1;i<=mark[0];i++){ans[i]+=mark[i];ans[i+1]+=ans[i]/1000000;ans[i]%=1000000;}while (ans[ans[0]+1]!=0){ans[0]++;ans[ans[0]+1]=ans[ans[0]]/1000000;ans[ans[0]]%=1000000;}return ;}else{if (-ans[0]>mark[0]) op=-1;else if (-ans[0]<mark[0]) op=1;else{for (i=mark[0];i>=1;i--)if (mark[i]>ans[i]) { op=1;break;}else if (mark[i]<ans[i]) { op=-1; break;}if (i==0){memset(ans,0,sizeof(ans));ans[0]=1;return ;}}if (op==1){for (i=1;i<=mark[0];i++){ans[i]=mark[i]-ans[i];if (ans[i]<0){mark[i+1]--;ans[i]+=1000000;}}ans[0]=-ans[0];while (ans[ans[0]]==0) ans[0]--;}else{for (i=1;i<=-ans[0];i++){ans[i]=ans[i]-mark[i];if (ans[i]<0){ans[i+1]--;ans[i]+=1000000;}}while (ans[-ans[0]]==0) ans[0]++;}}
}void make_red()
{int i,op;if (ans[0]<0){for (i=1;i<=mark[0];i++){ans[i]+=mark[i];ans[i+1]+=ans[i]/1000000;ans[i]%=1000000;}while (ans[-ans[0]+1]!=0){ans[0]--;ans[-ans[0]+1]=ans[-ans[0]]/1000000;ans[-ans[0]]%=1000000;}return ;}else{if (ans[0]>mark[0]) op=1;else if (ans[0]<mark[0]) op=-1;else{for (i=mark[0];i>=1;i--)if (mark[i]>ans[i]) { op=-1;break;}else if (mark[i]<ans[i]) { op=1; break;}if (i==0){memset(ans,0,sizeof(ans));ans[0]=1;return ;}}if (op==1){for (i=1;i<=mark[0];i++){ans[i]=ans[i]-mark[i];if (ans[i]<0){ans[i+1]--;ans[i]+=1000000;}}while (ans[ans[0]]==0) ans[0]--;}else{for (i=1;i<=mark[0];i++){ans[i]=mark[i]-ans[i];if (ans[i]<0){mark[i+1]--;ans[i]+=1000000;}}ans[0]=mark[0];while (ans[ans[0]]==0) ans[0]--;ans[0]=-ans[0];}}}
int main()
{int t,n,i,x,y,j,m,op;scanf("%d",&t);while (t--){scanf("%d",&n);for (i=1;i<=n;i++)scanf("%d",&a[i]);memset(ans,0,sizeof(ans));ans[0]=1;if (i==1){printf("%d\n",a[1]);continue;}memset(mark,0,sizeof(mark));mark[0]=1;mark[1]=1;if (n%2==1) ans[1]=a[1];else ans[1]=-a[1];x=1;y=n-1;for (i=2;i<=n;i++){make_mul(y);y--;make_div(x);x++;memcpy(c,mark,sizeof(mark));make_mul(a[i]);if (n%2==1){if (i%2==1) make_add();else make_red();}else{if (i%2==0) make_add();else make_red();}memcpy(mark,c,sizeof(c));}if (ans[0]>0){printf("%I64d",ans[ans[0]]);for (i=ans[0]-1;i>=1;i--)printf("%06I64d",ans[i]);printf("\n");}else{printf("-");printf("%I64d",ans[-ans[0]]);for (i=-ans[0]-1;i>=1;i--)printf("%06I64d",ans[i]);printf("\n");}}return 0;
}

这篇关于HDU 4927 大数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---