题意：度熊面前有一个全是由1构成的字符串，被称为全1序列。你可以合并任意相邻的两个1，从而形成一个新的序列。对于给定的一个全1序列，请计算根据以上方法，可以构成多少种不同的序列。最多200个1。
比如：如果序列是：(111)。可以构造出如下三个新序列：(111), (21), (12)。
分析：对于任意的相邻的两个1合并，那么总的个数就会减1，然后把2放在任意一个位置，也就是说，如果有x个2，那么总的数字个数就是n-x，相当于在这n-x中选择x个变成2，那么显然是组合数求解，在枚举x的个数即可。
但是，考虑到最大范围是200，会超long long，所以直接套大数模板就可以了。
下面是AC代码：
#include<stdio.h>
#include<string>
#include<string.h>
#include<iostream>
using namespace std; //compare比较函数：相等返回0，大于返回1，小于返回-1
int compare(string str1,string str2)
{
if(str1.length()>str2.length()) return ;
else if(str1.length()<str2.length()) return -;
else return str1.compare(str2);
}
//高精度加法
//只能是两个正数相加
string add(string str1,string str2)//高精度加法
{
string str; int len1=str1.length();
int len2=str2.length();
//前面补0，弄成长度相同
if(len1<len2)
{
for(int i=;i<=len2-len1;i++)
str1=""+str1;
}
else
{
for(int i=;i<=len1-len2;i++)
str2=""+str2;
}
len1=str1.length();
int cf=;
int temp;
for(int i=len1-;i>=;i--)
{
temp=str1[i]-''+str2[i]-''+cf;
cf=temp/;
temp%=;
str=char(temp+'')+str;
}
if(cf!=) str=char(cf+'')+str;
return str;
}
//高精度减法
//只能是两个正数相减，而且要大减小
string sub(string str1,string str2)//高精度减法
{
string str;
int tmp=str1.length()-str2.length();
int cf=;
for(int i=str2.length()-;i>=;i--)
{
if(str1[tmp+i]<str2[i]+cf)
{
str=char(str1[tmp+i]-str2[i]-cf+''+)+str;
cf=;
}
else
{
str=char(str1[tmp+i]-str2[i]-cf+'')+str;
cf=;
}
}
for(int i=tmp-;i>=;i--)
{
if(str1[i]-cf>='')
{
str=char(str1[i]-cf)+str;
cf=;
}
else
{
str=char(str1[i]-cf+)+str;
cf=;
}
}
str.erase(,str.find_first_not_of(''));//去除结果中多余的前导0
return str;
}
//高精度乘法
//只能是两个正数相乘
string mul(string str1,string str2)
{
string str;
int len1=str1.length();
int len2=str2.length();
string tempstr;
for(int i=len2-;i>=;i--)
{
tempstr="";
int temp=str2[i]-'';
int t=;
int cf=;
if(temp!=)
{
for(int j=;j<=len2--i;j++)
tempstr+="";
for(int j=len1-;j>=;j--)
{
t=(temp*(str1[j]-'')+cf)%;
cf=(temp*(str1[j]-'')+cf)/;
tempstr=char(t+'')+tempstr;
}
if(cf!=) tempstr=char(cf+'')+tempstr;
}
str=add(str,tempstr);
}
str.erase(,str.find_first_not_of(''));
return str;
} //高精度除法
//两个正数相除，商为quotient,余数为residue
//需要高精度减法和乘法
void div(string str1,string str2,string "ient,string &residue)
{
quotient=residue="";//清空
if(str2=="")//判断除数是否为0
{
quotient=residue="ERROR";
return;
}
if(str1=="")//判断被除数是否为0
{
quotient=residue="";
return;
}
int res=compare(str1,str2);
if(res<)
{
quotient="";
residue=str1;
return;
}
else if(res==)
{
quotient="";
residue="";
return;
}
else
{
int len1=str1.length();
int len2=str2.length();
string tempstr;
tempstr.append(str1,,len2-);
for(int i=len2-;i<len1;i++)
{
tempstr=tempstr+str1[i];
tempstr.erase(,tempstr.find_first_not_of(''));
if(tempstr.empty())
tempstr="";
for(char ch='';ch>='';ch--)//试商
{
string str,tmp;
str=str+ch;
tmp=mul(str2,str);
if(compare(tmp,tempstr)<=)//试商成功
{
quotient=quotient+ch;
tempstr=sub(tempstr,tmp);
break;
}
}
}
residue=tempstr;
}
quotient.erase(,quotient.find_first_not_of(''));
if(quotient.empty()) quotient="";
}
string c[][];
void init()
{
for(int i=;i<=;i++)
for(int j=;j<=;j++) c[i][j]="";
c[][]="";
c[][]=c[][]="";
for(int i=;i<=;i++)
{
for(int j=;j<=i;j++)
{
if(j==||j==i) c[i][j]="";
else c[i][j]=add(c[i][j],add(c[i-][j],c[i-][j-]));
}
}
}
int main()
{
init();
/*string str1,str2;
string str3,str4;
while(cin>>str1>>str2)
{
cout<<add(str1,str2)<<endl;
cout<<sub(str1,str2)<<endl;
cout<<mul(str1,str2)<<endl;
div(str1,str2,str3,str4);
cout<<str3<<" "<<str4<<endl;
}*/
int n;
while(scanf("%d",&n)==)
{
string ans="";
for(int i=n;i>=(n+)/;i--)
{
ans=add(ans,c[i][n-i]);
}
cout<<ans<<endl;
}
return ;
}
这是kuangbin的大数模板，以后就用这份模板好了- -