将n行匹配到m种韵脚里。
dp[i][j]表示将i行匹配到j种韵脚里的方案数。
转移方程:
dp[i][j]=dp[i-1][j-1]+dp[i-1][j]*j
初始化:
dp[i][1]=1
dp[1][i]=0 (i>=2)
由于没有告知数据范围,为保险使用了高精。
#include<cstdio>
#include<cstring>
using namespace std;
int maxf(int x,int y){return x>y?x:y;}
int minf(int x,int y){return x<y?x:y;}
char s[256];
int buf[256],tail;
struct hugeint
{
int a[256],i;
void clear()
{
memset(a,0,sizeof(a));
a[0]=1;
return;
}
void setnum(int x)
{
memset(a,0,sizeof(a));
tail=0;
while(x)
{
buf[++tail]=x%10;
x/=10;
}
for(i=tail;i>=1;i--)
a[tail-i+1]=buf[i];
a[0]=tail;
return;
}
void read()
{
scanf("%s",s+1);
a[0]=strlen(s+1);
for(i=a[0];i>=1;i--)
a[a[0]-i+1]=s[i]-'0';
return;
}
};
void writeint(hugeint x)
{
int i;
for(i=x.a[0];i>=1;i--)
printf("%d",x.a[i]);
return;
}
hugeint add(hugeint x,hugeint y)
{
int i,j,lenx,leny,k;
hugeint z;
z.clear();
lenx=x.a[0];leny=y.a[0];
k=maxf(lenx,leny);
for(i=1;i<=k;i++)
{
z.a[i]=x.a[i]+y.a[i];
}
for(i=1;i<=k-1;i++)
{
//printf("pos %d was:%d ",i,z.a[i]);
if(z.a[i]>=10)
{
z.a[i+1]+=z.a[i]/10;
z.a[i]%=10;
}
//printf("and:%d\n",z.a[i]);
}
while(z.a[k]>=10)
{
//printf("pos %d was:%d ",k,z.a[k]);
z.a[k+1]+=z.a[k]/10;
z.a[k]%=10;
k++;
//printf("and:%d\n",z.a[k]);
}
z.a[0]=k;
//printf("digits:%d\n",z.a[0]);
while(z.a[z.a[0]])z.a[0]++;
//printf("digits:%d\n",z.a[0]);
while(!z.a[z.a[0]])z.a[0]--;
//printf("digits:%d\n",z.a[0]);
return z;
}
hugeint multiply(hugeint x,int y)
{
int i,j,lenx,k;
hugeint z;
z.clear();
lenx=x.a[0];
k=lenx;
for(i=1;i<=k;i++)
{
z.a[i]=x.a[i]*y;
}
for(i=1;i<=k-1;i++)
{
if(z.a[i]>=10)
{
z.a[i+1]+=z.a[i]/10;
z.a[i]%=10;
}
}
while(z.a[k]>=10)
{
z.a[k+1]+=z.a[k]/10;
z.a[k]%=10;
k++;
}
z.a[0]=k;
while(z.a[z.a[0]])z.a[0]++;
while(!z.a[z.a[0]])z.a[0]--;
return z;
}
hugeint dp[100][100];
int main()
{
int n,m,i,j,k,x,y,z;
hugeint ans;
for(i=1;i<=99;i++)dp[i][1].setnum(1);
for(i=2;i<=99;i++)dp[1][i].clear();
while(1)
{
scanf("%d",&n);
if(n==0)break;
for(i=2;i<=n;i++)
{
for(j=2;j<=i;j++)
dp[i][j]=add(dp[i-1][j-1],multiply(dp[i-1][j],j));
}
ans.setnum(0);
for(i=1;i<=n;i++)
{
ans=add(ans,dp[n][i]);
}
printf("%d ",n);
writeint(ans);
printf("\n");
}
return 0;
}