hdu 2512一卡通大冒険【dp】【第二類スターリング数】
一卡通の大冒険
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1928 Accepted Submission(s): 1284
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
Sample Output
n個のカードは、せいぜいn個の本の中に置くことができ、少なくとも1冊の本の中に置くことができ、私たちはS(n,k)がn個のカードをk本の中に置く方法がどれだけあるかを規定している.
ここでans【n】=S(n,1)+S(n,2)+....................+S(n,n);
S(n,1)=1;S(n,n)=1;
特殊な討論S(n,k)【ここでkは2からn-1まで】;
2つの可能性があります
私たちはn個のカードの中から勝手に1個のカードを取り出して、この時カードは2つの部分に分けて、一部はn-1で、一部は1で、この1について討論する2つの可能性があります:
1、単独で1冊の本の中に分けて、n-1の部分はk-1の本の中に分けて、この情況はS(N-1、k-1)と表します;
2、n-1冊の本と一緒に(k冊の本の中に置く)、S(n-1,k)、このカードにはK種類の置き方があるからです.したがってK*S(n-1,k)と表す.
すなわち、その動的遷移方程式は、S(n,k)【2<=k<=n−1】=S(n−1,k−1)+k*S(n−1,k);
書き出しコードに対応します.残りの部分を忘れないでください:
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1928 Accepted Submission(s): 1284
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
n個のカードは、せいぜいn個の本の中に置くことができ、少なくとも1冊の本の中に置くことができ、私たちはS(n,k)がn個のカードをk本の中に置く方法がどれだけあるかを規定している.
ここでans【n】=S(n,1)+S(n,2)+....................+S(n,n);
S(n,1)=1;S(n,n)=1;
特殊な討論S(n,k)【ここでkは2からn-1まで】;
2つの可能性があります
私たちはn個のカードの中から勝手に1個のカードを取り出して、この時カードは2つの部分に分けて、一部はn-1で、一部は1で、この1について討論する2つの可能性があります:
1、単独で1冊の本の中に分けて、n-1の部分はk-1の本の中に分けて、この情況はS(N-1、k-1)と表します;
2、n-1冊の本と一緒に(k冊の本の中に置く)、S(n-1,k)、このカードにはK種類の置き方があるからです.したがってK*S(n-1,k)と表す.
すなわち、その動的遷移方程式は、S(n,k)【2<=k<=n−1】=S(n−1,k−1)+k*S(n−1,k);
書き出しコードに対応します.残りの部分を忘れないでください:
#include<stdio.h>
#include<string.h>
using namespace std;
#define mod 1000
int dp[2002][2002];
int ans[2002];
int main()
{
memset(dp,0,sizeof(dp));
for(int i=1;i<=2000;i++)
{
dp[i][0]=0;
dp[i][i]=1;
for(int j=1;j<i;j++)
{
dp[i][j]=(dp[i-1][j-1]+j*dp[i-1][j])%mod;
}
}
for(int i=1;i<=2000;i++)
{
ans[i]=0;
for(int j=1;j<=i;j++)
{
ans[i]=(ans[i]+dp[i][j])%mod;
}
}
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
printf("%d
",ans[n]);
}
}