Submission #974422

#	Time	Username	Problem	Language	Result	Execution time	Memory
974422		Sharky	Asceticism (JOI18_asceticism)	C++17	49 / 100	32 ms	25152 KiB

asceticism

// dp[i][j] -> dp[i+1][j] * j
// dp[i][j] -> dp[i+1][j+1] * (i-j+1);

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int mod = 1e9 + 7;

int dp[3002][3002];
int n, k;

int32_t main() {
    int n, k;
    cin >> n >> k;
    dp[0][0] = 1;
    for (int i = 0; i <= n; i++) for (int j = 0; j <= k; j++) {
        dp[i+1][j] += dp[i][j] * j % mod;
        dp[i+1][j] %= mod;
        dp[i+1][j+1] += dp[i][j] * (i-j+1) % mod;
        dp[i+1][j+1] %= mod;
    }
    cout << dp[n][k] << '\n';
}

• Subtask 1: 4 / 4
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 0 / 51