HDOJ 2512-一卡通大冒险【组み合わせ数学】


一卡通大冒険Time Limit:2000/1000 MS(Java/others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1876    Accepted Submission(s): 1250
Problem Description
長期にわたってアルゴリズムを研究し、個人的な問題を考慮する暇がないため、BUAA ACM/ICCCトレーニングチームのイケメンたちの大部分は独身だ.ある日、彼らは機械室で絶妙な計画「一卡通大冒険」を相談した.この計画はwfが最初に提出したもので、計画の内容は、自分の連絡先をキャンパスの一卡通の裏に書いて、それからわざと自分のカードを「紛失」してどこか(例えば水房、TD、食堂、主M....)彼らはMMが彼らの紛失カードを見て、自発的に彼らと連絡することができることを望んで、このようにMMに食事をごちそうする機会があります.彼らは自分の漫画を基本的に同じ本に挟んで、キャンパスの隅々に本をなくすことにした.この絶妙な計画のためにみんなが呼んだとき,みんなは一つの問題を思いついた.明らかに、1枚の漫画しかない場合は、1冊の本に挟む方法しかありません.1枚の漫画が2枚あると、2つの選択肢があります.つまり、2枚の1枚の漫画を1冊の本に挟んだり、別の本に挟んだりします.一卡通が3枚あると、5つの選択肢があります.
{{A},{B},{C}},{A,B},{C},{B,C},{A,{B},{B},{A,C},{B},{A,B,C}}すると,
この邪悪な計画の組織者wfは、ACM訓練ペアにn人のイケメン(つまりN枚の漫画がある)がいれば、これらの漫画を本に挟むにはどのような方法があるかを知りたいと思っています.
 
Input
複数のデータのセットが含まれ、第1の動作nは、次にnのデータのセットがあることを示す.以下の行ごとに1つの数xで、x枚の漫画が共有されていることを示します.(1≤x≤2000).
 
Output
各グループのデータに対して、1行を出力します.この数は非常に大きい可能性があるため、1000の余剰数で除算するだけです.
 
Sample Input

       
       
       
       

        
        
        
        4
1
2
3
100
       
       
       
       

 
Sample Output

       
       
       
       

        
        
        
        1
2
5
751
       
       
       
       

 
Author
BUAA Campus 2007
 

S(n,k)   n        k       ，               。
   ：S(n,k)=S(n-1,k-1)+k*S(n-1,k)，S(1,1)=1，S(n,n)=1。

       Sum(n)=S(n,1)+S(n,2)+S(n,3)+...+S(n,k-1)+S(n,k)，   sum[]   Sum(n)，           。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int map[2001][2001];
int main()
{
	int i,j,sum,n;
	memset(map,0,sizeof(map));
	map[1][1]=1;
	for(i=2;i<2001;i++)
	{
		for(j=1;j<=i;j++)
		{
			map[i][j]=map[i-1][j]*j+map[i-1][j-1];
			map[i][j]%=1000;		
		}
	}
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int cnm;
		scanf("%d",&cnm);
		sum=0;
		for(i=1;i<=cnm;i++)
		{
			sum+=map[cnm][i];
			sum%=1000;
		}
		printf("%d
",sum);
	}
	return 0;
}