PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter and Editorialist: Soumyadeep Pal
Testers: Takuki Kurokawa, Tejas Pandey
DIFFICULTY:
3336
PREREQUISITES:
Dynamic Programming, MEX
PROBLEM:
A function F is defined on an array A of length N as follows:
F(A) = \sum_{i=1}^{N} MEX(A_1+A_2+\dots+A_i)
For example, if A = [2, 0, 1], then F(A) = MEX([2]) + MEX([2,0]) + MEX([2,0,1]) = 0 +1 +3 = 4.
You are given two integers N and K. For each i = N, N + 1, \dots, K in order, find the number of permutations P of integers [0, 1, 2, \dots, N - 1] such that F(P) = i. Since the answer can be very large, find it modulo (10^9+7).
EXPLANATION:
Hint
Try to put the elements 0, 1, 2, \dots, N - 1 in order and see how the value of F(A) changes for putting a new element in the permutation
Solution
Let’s say Pre_j denotes the prefix of length j of the permutation P and Mex_j denotes the mex of Pre_j. Thus F(A) = Mex_1 + Mex_2 + \dots + Mex_N.
Initially consider that the permutation P is empty. Hence Mex_j = 0 for each 1 \le j \le N, as the mex of an empty array is 0. Thus F(A) = 0. Now we put the elements from 0 to N - 1 in order.
Say we put the element 0 on index id_0. Now for all indices j = id_0, id_0 + 1,\dots, N, Pre_j will contain the element 0 making Mex_j = 1, for the rest indices Mex_j remains 0. So putting the element 0 on index id_0 increase the value of F(A) by N - id_0 + 1.
Now we put the element 1 on index id_1(id_1 \neq id_0). Here two cases occur:
-
id_1 \lt id_0 : For all indices j = id_0, id_0 + 1,\dots, N, Pre_j will contain the element 0, 1 making Mex_j = 2. So putting the element 1 on index id_1 increases the value of F(A) by N - id_0 + 1, because for each id_0 \le j \le N the value of Mex_j becomes 2 from 1, Mex_j remains unchanged for the remaining indices.
-
id_1 \gt id_0: For all indices j = id_1, id_1 + 1, \dots, N, Pre_j will contain the element 0, 1 making Mex_j = 2. So putting the element 1 on index id_1 increases the value of F(A) by N - id_1 + 1 because for each id_1 \le j \le N the value of Mex_j becomes 2 from 1, Mex_j remains unchanged for the remaining indices.
Let’ say Mx_1 = \max(id_0, id_1). Then putting 1 on index id_1 increases the value of F(A) by N - MX_1 + 1.
If we put the element 2 on index id_2 and Mx_2 = \max(id_0, id_1, id_2), it will increase the value of F(A) by N - MX_2 + 1.
Let, Dp[i][Mx_i][S] = number of ways to put the elements 0, 1, \dots, i in a permutation of length N such that maximum position of these elements is Mx_i and the value of F(A) we get is S. So Dp[0][i][N-i+1] = 1 for each 1\le i \le N.
Say, we have put the elements 0, 1, 2, \dots, i - 1 on positions id_0, id_1,\dots, id_{i - 1} respectively, the current value of F(A) is S. Now we put the element i on index id_i and Mx_i = \max(id_0, id_1,\dots, id_i). It will increase the value of F(A) by N - mx[i] + 1. Here two cases may occur:
- id_i = Mx_i (i.e . we put the element i on index Mx_i): The maximum position among 0, 1,\dots, i-1 (i.e. Mx_{i - 1}) can lie in the range [1, Mx_i - 1]. Thus we will do: Dp[i][Mx_i][S + N - Mx_i + 1] += \sum_{j = 1}^{Mx_i - 1} Dp[i - 1][j][S].
- id_i \lt Mx_i (i.e one of 0,1, \dots, i - 1 on position Mx_i): We have put 0,1, \dots, i - 1 among the first Mx_i positions from left. Hence we can put the element i on one of the Mx_i - i positions. Thus we will do: Dp[i][Mx_i][S+ N - Mx_i + 1] += Dp[i-1][Mx_i][S] * (Mx_i - i).
So the number of permutations P of length N with F(A) = i will be Dp[N-1][N][i].
.
TIME COMPLEXITY:
O(N^2 \cdot K) for each test case.
SOLUTION:
Setter's solution
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
void add(int &a, int b) {
a = (a + b) % mod;
}
int mul (int a, int b) {
return 1LL * a * b % mod;
}
int32_t main() {
int n, k;
cin >> n >> k;
vector<vector<int>> dp(n + 1, vector<int>(k + 1));
for (int i = 1; i <= n; i++) {
dp[i][n - i + 1] = 1;
}
for (int i = 1; i < n; i++) {
vector<vector<int>> ndp(n + 1, vector<int>(k + 1));
for (int s = 1; s <= k; s++) {
int sum = 0;
for (int mx_pos = 1; mx_pos <= n; mx_pos++) {
int ns = s + n - mx_pos + 1;
// i is on new mx_pos
if (ns <= k) {
add(ndp[mx_pos][ns], sum);
}
// i is put on position < mx_pos (one of 0, 1, ..., i - 1 is on mx_pos)
if (ns <= k && mx_pos > i) {
add(ndp[mx_pos][ns], mul(mx_pos - i, dp[mx_pos][s]));
}
add(sum, dp[mx_pos][s]);
}
}
dp = ndp;
}
for (int i = n; i <= k; i++) {
cout << dp[n][i] << " \n"[i == k];
}
return 0;
}
Tester 1's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
const long long mod = (long long) 1e9 + 7;
int n, k;
cin >> n >> k;
vector<vector<long long>> dp(n + 1, vector<long long>(k + 1));
dp[0][0] = 1;
for (int i = 0; i < n; i++) {
vector<vector<long long>> new_dp(n + 1, vector<long long>(k + 1));
for (int y = 0; y <= k; y++) {
long long sum = 0;
for (int x = 0; x <= min(n, k - y); x++) {
new_dp[x][y + x] += sum;
new_dp[x][y + x] += dp[x][y] * (i + 1 - x);
new_dp[x][y + x] %= mod;
sum += dp[x][y];
}
}
swap(dp, new_dp);
}
for (int i = n; i <= k; i++) {
if (i > n) {
cout << " ";
}
cout << dp[n][i];
}
cout << endl;
return 0;
}
Tester 2's Solution
#include <bits/stdc++.h>
#define mxn 157
#define mxk 2007
#define mod 1000000007
#define ll long long int
using namespace std;
ll dp[mxn][mxn][mxk];
int main() {
int n, k;
cin >> n >> k;
dp[0][n][0] = 1;
for(int i = 1; i <= n; i++) {
int pre[n + 2][k + 1];
memset(pre, 0, sizeof(pre));
for(int j = 0; j <= k; j++) {
for(int l = n; l; l--) {
pre[l][j] += pre[l + 1][j];
pre[l][j] += dp[i - 1][l + 1][j];
pre[l][j] %= mod;
}
}
for(int j = 1; j <= n + 1 - i; j++) {
for(int l = k - j; l > -1; l--) {
dp[i][j][l + j] += pre[j][l];
dp[i][j][l + j] %= mod;
dp[i][j][l + j] += ((dp[i - 1][j][l])*(n + 2 - i - j))%mod;
dp[i][j][l + j] %= mod;
}
}
}
for(int i = n; i <= k; i++) {
ll ans = 0;
for(int j = 0; j <= n; j++) ans += dp[n][j][i], ans %= mod;
cout << ans << " ";
}
return 0;
}