题解 P2401 【不等数列】

2018-08-18 16:31:29


#include <cstdio>

const int MaxN = 1e3;
const int MaxK = 1e3;
const int Mod = 2015;

int main() {
    int n, k;
    scanf("%d %d", &n, &k);

    static int dp[MaxN + 1][MaxK + 1];
    dp[1][0] = 1;
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * (j + 1)) % Mod;
            dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j] * (i - j)) % Mod;
        }
    }

    printf("%d\n", dp[n][k]);
}