hdu 2512-一卡通大冒険

一卡通の大冒険
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1383    Accepted Submission(s): 914
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
 
Source
ECJTU 2008 Autumn Contest
 
Recommend
lcy   |   We have carefully selected several similar problems for you:   2509  2516  2515  2510  2517
簡単dp、i番目の品物を考慮して、彼は単独で1冊の本の中に置くことができます(前i-1形成 j-1グループ)は、前i-1個とjグループに分けて、どの本に入れてもかまいません.
だから状態方程式がある
   dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] * j

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

__int64 dp[2010][2010];

int main()
{
	int t, n;
	scanf("%d", &t);
	while( t-- )
	//while(~scanf("%d", &n))
	{
		scanf("%d", &n);
		memset(dp, 0, sizeof(dp));
		dp[0][0] = 1;
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
			{
				if( i == j || j == 1)
					dp[i][j] = 1;
				else
				{
					dp[i][j] = dp[i - 1][j - 1] + j * dp[i - 1][j];
					dp[i][j] %= 1000;
				}
					
			}
		__int64 ans = 0;
		for(int i = 1; i <= n; i++)
		{
			ans += dp[n][i];
			ans %= 1000;
		}	
		printf("%I64d
", ans);
	}
	return 0;
}