大数 Astar-Round1 Problem B

题目

2016"百度之星" - 资格赛（Astar Round1）

http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=690&pid=1002

Problem Description

如果序列是：(111)。可以构造出如下三个新序列：(111),(21),(12)。

分析

n-i个位置中放置i个2。要计算组合，由于N较大，最后结果远超long long能存储范围，所以涉及大数加法、乘法、除法。

（这个代码运行时间相对较长，不是很有参考性）

（比赛还没结束，但这篇文章能被搜索引擎收录时应该结束了吧）

代码

#include <iostream>
using namespace std;
const int SZ=50;

int ans[SZ];
int c[SZ];

void mul(int a[],int m)
{
	for(int i=0;i<SZ-2;i++){
		a[i]*=m;
	}
	for(int i=1;i<SZ-2;i++){
		a[i]+=a[i-1]/10;
		a[i-1]%=10;
	}
}

void div(int a[],int m)
{
	int i,c;
	for(i=SZ-2,c=0;i>=0;i--){
		c=c*10+a[i];
		a[i]=c/m;
		c%=m;
	}
}

void add(int a[],const int b[])
{
	int i;
	for(i=0;i<SZ-2;i++){
		a[i]+=b[i];
		a[i+1]+=a[i]/10;
		a[i]%=10;
	}
	if(a[SZ-1])
		cout<<"spill"<<endl;
}

void zero(int a[])
{
	for(int i=0;i<SZ;i++)
		a[i]=0;
}

void print(int a[])
{
	int i,j;
	for(i=SZ-1;i>=0;i--)
		if(a[i])
			break;
	for(j=i;j>=0;j--)
		cout<<a[j];
	cout<<endl;
}

int main()
{
	int i,j;
	int n;
	while(cin>>n){
		zero(ans);
		ans[0]=1;
		for(i=1;2*i<=n;i++){
			zero(c);
			c[0]=1;
			for(j=1;j<=min(i,n-2*i);j++){
				mul(c,n-i-j+1);
				div(c,j);
			}
			add(ans,c);
		}
		print(ans);
	}
	return 0;
}

（编辑：佛山站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!