PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Isaac Moris
Tester: Rahul Dugar
Editorialist: Aman Dwivedi
DIFFICULTY:
Medium
PREREQUISITES:
DP, Expected-Value
PROBLEM
An array A=[A_1 , A_2 , \ldots , A_n] is said to be a hill array if there exists an integer p, (1 \leq p \leq n) such that, (0 \leq A_1 \leq A_2,\dots \leq A_p \geq A_{p+1} \dots \geq A_n \geq 0). For an array A and an integer K we define F(A, K) = \sum_{i=1}^{n} A_i^K. For purposes of this problem we consider 0^0 = 1.
You are given N, M and K, consider all hill arrays of size N having sum of elements equal to M (\sum_{i=1}^{N} A_i = M). You will choose one of them equiprobably at random as array A. Your task is to find the expected value of F(A, K) modulo 10^9 + 7?
EXPLANATION:
Suppose there exists X hill arrays of length N having the sum of elements equal to M. Let S_1,S_2, \dots, S_X be the F(A, K) values for those arrays. Since choosing any array is equiprobable hence the probability for selecting any one of the arrays at random is \large \frac{1}{X}. Thus the Expected Value will be:
How to get the number of Hill Arrays of length N having the sum of elements equal to M?
We can use Dynamic Programming to find the number of such arrays. Let’s move towards it:
DP[len][S] is defined as the number of hill arrays of length N having the sum of elements equal to S. From this state i.e. (len, S) we can move to either of the states:
-
Increment all the elements in the array by 1, thus moving to the state (len, S+len). Since adding the same integer on all the elements of the Hill array is again the Hill Array.
-
We can expand the size of the array by 1 by placing 0 in the left or right thus moving to the state (len+1, S).
Also notice that we can go to the state (len+1, S) from state (len, S) in 2 ways. Hence there will be 4 ways to go to the state (len+2, S) from state (len, S). But there are only 3 ways to go to the state (len+2, S) from state (len, S).
Why only 3 times?
It is quite simple to observe that. Suppose we have an array A of length 2 as [A_1, A_2]. Now we expand the size of the array by 1 by placing 0 in the left or right. Hence our new arrays of length 3 will be:
Since both of the arrays are distinct, hence there are 2 possible ways to expand the size. Now let us again try to expand the size of the array by 1, we get arrays as:
The arrays that can be formed from [0,A_1,A_2] are:
The arrays that can be formed from [0,A_1,A_2] are:
We can see that the array [0,A_1,A_2,0] is repeated two times. Hence there are only 3 ways to reach state (len+2, S) from state (len, S)
So our DP will be:
DP[N][M] tells the number of Hill arrays of length N having the sum of elements equal to M.
How to get the Sum of F(A, K) for all Hill arrays?
Case 1: K=0
Since K=0, it means that for any element of array A_i we will get A_i^K=1 (0^0=1 is considered for this problem). Hence the F(A, K) for any of the hill array will be the length of the array i.e N. So simply we will find the number of such Hill arrays and multiply it by N to get the sum of F(A, K) for all Hill arrays.
Case 2: K>0
We can use Dynamic Programming to find the Sum of F(A, K) of such arrays. Let’s move towards it:
DP[len][S][K] is defined as the sum of F(A, K) for all the hill arrays of length N having the sum of elements equal to S. From this state i.e. (len, S, K) we can move to either of the states:
- By incrementing all the elements of the array A by 1. Initially F(A, K) is:
\hspace{0.8cm} Now we increment all the elements by 1 hence we get a new array B. Then F(B,K) will \hspace{0.8cm} be:
\hspace{0.8cm} We can use Binomial Theorem to expand it as:
- We can expand the size of the array by 1 by placing 0 in the left or right thus moving to the state (len+1, S, K).
So our DP will be:
DP[N][M][K] tells the sum of F(A, K) of Hill arrays of length N having the sum of elements equal to M.
We can divide the above sum by the number of Hill arrays of length N having the sum of elements equal to M to get the expected value of F(A, K).
TIME COMPLEXITY:
O(N*M*K^2) for each test case
SOLUTIONS:
Setter
// Sometimes, the questions are complicated - and the answers are simple. //
#include<iostream>
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 1e3 + 2, mod = 1e9 + 7, K = 22;
int fp(int b, int p, int mod) {
if(p == 0)
return 1;
int ans = fp(1LL * b * b % mod, p / 2, mod);
return p % 2 ? 1LL * ans * b % mod : ans;
}
void add(int &x, int y) {
x = (x + y) % mod;
}
int n, m, k;
int p[N][K]; // p[i][j] = i power j
int ncr[K][K];
int dpcount[N][N], dpsum[N][N][K];
void preprocess() {
p[0][0] = 1;
for(int j = 0; j < K ; j++)
for(int i = 1; i < N; i++) {
p[i][j] = (j == 0 ? 1 : 1LL * i * p[i][j - 1] % mod);
}
for(int i = 0; i < K; i++)
ncr[i][0] = 1;
for(int i = 1; i < K; i++)
for(int j = 1; j <= i; j++)
ncr[i][j] = (ncr[i - 1][j] + ncr[i - 1][j - 1]) % mod;
}
void solve(int n, int m, int k) {
preprocess();
dpcount[0][0] = 1;
for(int rem = 0; rem <= m; rem++) {
for(int i = 0; i <= k; i++) {
dpsum[1][rem][i] = p[rem][i];
}
dpcount[1][rem] = 1;
}
for(int len = 2; len <= n; len++) {
for(int rem = 0; rem <= m ; rem++) {
// Case k=0
{
dpcount[len][rem] = (2LL * dpcount[len - 1][rem] - 1LL * dpcount[len - 2][rem] + mod) % mod;
if(rem - len >= 0)
add(dpcount[len][rem], dpcount[len][rem - len]);
dpsum[len][rem][0] = 1LL * len * dpcount[len][rem] % mod;
}
// Case k >=1
{
for(int i = 1; i <= k; i++) {
//---------------------------- -Decrease L or R------------------------------------------ -
dpsum[len][rem][i] = (2LL * dpsum[len - 1][rem][i] - dpsum[len - 2][rem][i] + mod) % mod;
// -------------------------------------------------------------------------------------- -
//--------------------------Increase Current Length by +1--------------------------------
if(rem - len >= 0) {
for(int j = 0; j <= i; j++) {
add(dpsum[len][rem][i], 1LL * ncr[i][j] * dpsum[len][rem - len][j] % mod);
}
}
//---------------------------------------------------------------------------------------
}
}
}
}
}
int main() {
IO
int Tc;
solve(1000, 1000, 20);
cin >> Tc;
while(Tc--) {
cin >> n >> m >> k;
cout << 1LL * dpsum[n][m][k]*fp(dpcount[n][m], mod - 2, mod) % mod << "\n";
}
}
Tester
Editorialist