XDU-1112 Too Stupid(DP)

1112: Too Stupid

Time Limit: 1 Sec  
Memory Limit: 128 MB
[ Submit][ Status][ Web Board]

Description

어느 날 라이트는 너무 부유하고 너무 멋있어서 악당들의 습격을 받았다. 현재 그는 n명의 악당을 만나 라이트에 대해 불법 행위를 하려고 한다. 비록 라이트는 몸이 강하지만 한 사람만 그렇게 많은 악당을 이길 수 없을 것이다. 그러나 지능이 높은 라이트는 악당들이 비정상적으로 stupid를 하고 꼼짝 못하고 잡히려고 하지 않는다.관찰한 결과 이 악당들이 파벌의 구분이 있다는 것을 알게 된 우리는 A와 B, B와 C를 같은 파벌로 규정하고 있다. 그러면 A와 C도 같은 파벌인 라이트는 악당의 파벌 상황을 파악하면 특수한 계략으로 그들을 이길 수 있다고 주장했다.그러나 악당들 사이에 파벌이 형성될 가능성이 많은데 라이트는 이를 전혀 모른다.이제 문제가 생겼다. 악당들은 파벌을 형성할 수 있는 방안이 얼마나 많은가.프로젝트 수가 많을 수 있으므로 1000000007을 추출하여 출력하십시오.

Input

여러 데이터 그룹, EOF 처리
그룹당 데이터 첫 줄 정수 n 1 <=n <=1000

Output

출력 프로젝트 수, 1000000007(1e9+7) 추출

Sample Input

1
2
3

Sample Output

1
2
5

HINT

세 명의 악당의 상황:
1:A와 B는 같은 파벌, C는 다르다
2:B와 C는 같은 파벌, A는 다르다
3:A와 C는 같은 파벌, B는 다르다
4:A, B, C 세 사람 동파
5:A, B, C 세 사람은 모두 파벌이 다르다
주제에 넣으면 DP만 생각하고 오랫동안 생각했어요.1차원 상태에서 2차원 상태로 생각하다
사고 과정:
처음에는 1차원만 생각했어요.
i개인이 i-1사람보다 많은 사람은 할 수 있다: ① 자기 한 파벌 ② i-1사람이 나타난 파벌 중
① 상황은 옮기기 쉽지만 ② 하기 어렵다. 방안에 따라 파계수가 다르기 때문에 옮기는 방안도 다르다
그래서 상태를 2차원으로 표시하고 dp[i][j]는 i 개인 j개의 서로 다른 파벌이 얼마나 많은 방안이 있는지 나타낸다.
①:dp[i-1][j-1]
②: dp[i-1][j]*j(j개의 다른 파벌이 있기 때문에 제i개인이 j개의 파벌에 나타날 수 있다면 방안수는 j를 곱해야 한다)
이때 dp[i][j]=(dp[i-1][j-1]+dp[i-1][j]*j)가 있다.

#include <cstdio>
using namespace std;

const long long MOD=1000000007;
long long dp[1001][1002];//dp[i][j]  i  j           
int main() {
    int i,j,n;
    dp[1][0]=0,dp[1][1001]=dp[1][1]=1;
    for(i=2;i<1001;++i) {
        dp[i][0]=0,dp[i][1001]=dp[i][i]=1;
        for(j=1;j<i;++j) {
            dp[i][j]=(dp[i-1][j-1]+dp[i-1][j]*j)%MOD;//       ，      long long 
            if((dp[i][1001]+=dp[i][j])>=MOD)
                dp[i][1001]-=MOD;
        }
    }
    while(1==scanf("%d",&n))
        printf("%lld
",dp[n][1001]);//XDU  long long  lld   Output Limit Exceed，           ...
    return 0;
}