前做過這類題的迷你版，n最大值只有25。這道題雖然是2000，但是絲毫不能影響我用樣的方法把它切了。
重復一下之前的解釋：n張卡分組一共只有n種情況，分別是分一組，兩組，三組。。。n組。將i張卡分成j組可以有之前兩種情況得來：i-1張卡分成j-1組，只要將第i張卡獨立分成一組就行了，或者是i-1張卡分成j組，第i張卡隨便插入哪一組都符合條件。
狀態轉移方程：mark[i][j]=mark[i-1][j-1]+mark[i-1][j]*j。
[cpp]
#include<stdio.h>
#include<string.h>
#define N 2005
int mark[N][N];
int main()
{
int i,j;
memset(mark,0,sizeof(mark));
for(i=1;i<=2000;i++)
{
mark[i][1]=1;
mark[i][0]=0;
for(j=1;j<=2000;j++)
{
if(i==j)
{
mark[i][j]=1;
continue;
}
mark[i][j]=mark[i-1][j-1]+mark[i-1][j]*j;
mark[i][j]%=1000;
}
}
int n,T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int ans=0;
for(i=0;i<=n;i++)
ans+=mark[n][i];
printf("%d\n",ans%1000);
}
return 0;
}
#include<stdio.h>
#include<string.h>
#define N 2005
int mark[N][N];
int main()
{
int i,j;
memset(mark,0,sizeof(mark));
for(i=1;i<=2000;i++)
{
mark[i][1]=1;
mark[i][0]=0;
for(j=1;j<=2000;j++)
{
if(i==j)
{
mark[i][j]=1;
continue;
}
mark[i][j]=mark[i-1][j-1]+mark[i-1][j]*j;
mark[i][j]%=1000;
}
}
int n,T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int ans=0;
for(i=0;i<=n;i++)
ans+=mark[n][i];
printf("%d\n",ans%1000);
}
return 0;
}
