uva 12034 - Race(dp 계수)

4170 단어

제목 링크: uva 12034 - Race


제목 대의: n 말 시합이 있는데 몇 가지 랭킹 상황이 있는지 물어보면 병렬할 수 있다.
문제풀이 방향: dp[i][j]는 i마리의 말을 나타내고 꼴찌가 j인 경우 방정식 dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])를 옮긴다.
#include <cstdio>
#include <cstring>

typedef long long ll;
const int N = 1005;
const ll MOD = 10056;
ll dp[N][N], f[N];

void init () {
    memset(f, 0, sizeof(f));
    memset(dp, 0, sizeof(dp));
    dp[1][1] = 1;

    for (ll i = 1; i <= 1000; i++) {

        for (ll j = 1; j <= i; j++) {
            dp[i+1][j] = (dp[i+1][j] + dp[i][j] * j) % MOD;
            dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j] * (j + 1)) % MOD;
            f[i] = (f[i] + dp[i][j]) % MOD;
        }
    }
}

int main () {
    init();
    int cas, n;
    scanf("%d", &cas);
    for (int i = 1; i <= cas; i++) {
        scanf("%d", &n);
        printf("Case %d: %lld
"
, i, f[n]); } return 0; }

좋은 웹페이지 즐겨찾기