/*
比赛(Test):查看题目 Show Problem
赛题题目:自然的雪糕
所属比赛:回归自然模拟赛
问题编号:385 [提交该赛题]
描述: 题目背景
话说某天小岛从超市里买了许许多多的..雪糕....本来他打算存在冰箱里慢慢享用的...
结果这件事情被寝室里的adx发现了...于是不幸的事情发生了...
题目叙述
小岛回忆起了当时de场景...
那时...寝室里包括自己一共聚集了 n 个人...我从超市里共买了 m 袋不同种类的雪糕.....
醒来之后身边一支雪糕也没有了.....我还可以隐约知道...每个人都不会一支雪糕也不拿...
小岛想知道自己的雪糕现在会在哪...那么当时的情况下...一共有多少种不同的可能呢..?
数据规模
对于30% 的数据,n <= 10,m <= 20。
对于100%的数据, n <= 100,m<= 100。
样例解释
雪糕以 1-3 编号。共六种情况,其中三种为:
1. {1} {2, 3}
2. {2} {1, 3}
3. {3} {1, 2}
另三种与之对称。
输入格式: 一行两个数 n,m...
输出格式: 一个数表示当时可能的情况数目...
输入文件: 直接输入即可
输出文件: 直接输出即可 注意,不要在最后输出空行或空格!
样例输入: 3 3
样例输出: 6
*/
#include<iostream>
#define MAXN 100
#define MAXM 100
using namespace std;
struct mynode{
int len;
string data;
};
mynode dp[MAXM+1][MAXN+1];
//F(n,m)=F(n-1,m-1)+m*F(n-1,m)
mynode zero={1,"0"},one={1,"1"},fuyi={1,"fyi"};
mynode jia (mynode a,mynode b){
int jinwei=0,temp;
mynode c;
string aa,bb,cc="";
aa=a.data;
bb=b.data;
while (aa.size()<bb.size()) aa="0"+aa;
while (aa.size()>bb.size()) bb="0"+bb;
for (int i=aa.size()-1;i>=0;i--){
temp=jinwei+(int)(aa[i]-’0’)+(int)(bb[i]-’0’);
jinwei=temp/10;
temp%=10;
cc+=(char)(temp+’0’);
}
if (jinwei!=0)
cc=(char)(jinwei+’0’)+cc;
c.len=cc.size();
c.data=cc;
//cout<<"jia "<<a.data<<" "<<b.data<<"="<<c.data<<endl;
return c;
}
mynode cheng(mynode a,mynode b){
mynode temp=zero,ppp=b;
for (int i=a.data.size()-1;i>=0;i--){
for (int j=0;j<a.data[i]-’0’;j++)
temp=jia(temp,ppp);
ppp.len++;ppp.data=ppp.data+"0";
}
//cout<<"cheng "<<a.data<<" "<<b.data<<"="<<temp.data<<endl;
return temp;
}
mynode tonode(int n){
string temp="";
while (n){
temp=(char)(n%10+’0’)+temp;
n/=10;
}
mynode temp2;
temp2.len=temp.size();
temp2.data=temp;
return temp2;
}
mynode fac(int n){
if (n==1) return one;
return cheng(fac(n-1),tonode(n));
}
mynode output(mynode x){
cout<<x.data;
}
bool eq(mynode a){
if (a.data=="fyi")
return true;
return false;
}
mynode work (int m,int n){
if (!eq(dp[m][n])) return dp[m][n];
//mynode ans;
if (m<n) return zero;
if (m==n) return one;
if (n==0) return zero;
if (n==1) return one;
dp[m][n]=jia(work(m-1,n-1),cheng(tonode(n),work(m-1,n)));
return dp[m][n];
}
int main (void){
for (int i=0;i<=MAXN;i++)
for (int j=0;j<=MAXN;j++)
dp[i][j]=fuyi;
int n,m;cin>>n>>m;
--n;
//output(zero);cout<<’ ’;output(one);
output(cheng(work(m,n),fac(n)));
//while(1);
return 0;
}