Submission #528847

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
528847	2022-02-21 15:10:49	Leonardo_Paes	Asceticism (JOI18_asceticism)	C++17	49 / 100	44 ms	72220 KiB

asceticism

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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