Submission #528847

#	Time	Username	Problem	Language	Result	Execution time	Memory
528847		Leonardo_Paes	Asceticism (JOI18_asceticism)	C++17	49 / 100	44 ms	72220 KiB

asceticism

#include<bits/stdc++.h>
using namespace std;
/*
	Numero de permutacoes de tamanho n com k-1 descidas 
	n = 3, k = 2:
	1) 1 3 2 [1, 3], [2]
	2) 2 1 3 [2], [1, 3]
	3) 2 3 1 [2, 3], [1]
	4) 3 1 2 [3], [1, 2]
*/
typedef long long ll;
const int maxn = 3010, mod = 1e9 + 7;
int dp[maxn][maxn];

int solve(int n, int k){
	if(n == 1) return k == 1; 
	if(dp[n][k] != -1) return dp[n][k];
	ll tot = 1LL * solve(n-1, k) * k + 1LL * solve(n-1, k-1) * (n - k + 1);
	tot %= mod;
	return dp[n][k] = tot;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n, k;
	cin >> n >> k;
	memset(dp, -1, sizeof dp);
	cout << solve(n, k);
	return 0;
}

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