PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: munch_01
Tester: apoorv_me
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Combinatorics
PROBLEM:
You’re given an integer N.
For each K = 1, 2, 3, \ldots, N, find the number of permutations of [N] such that the quantity
is maximized.
EXPLANATION:
Let’s solve the problem for a fixed N and K.
First, observe that for a fixed permutation, any given element is included in at most K subarrays of length K (specifically, P_i is included in the subarrays starting at indices i, i-1, i-2, \ldots, i-K+1.)
So, each element can also be the maximum of at most K subarrays of length K.
To maximize the sum of maximums, clearly the best we can do is to have N be the maximum of K subarrays, N-1 to be the maximum of another K subarrays, and so on.
It’s not hard to see that this is indeed achievable, for example just by placing N, N-1, N-2, \ldots at indices K, 2K, 3K, \ldots (and putting the smaller elements in any order).
Now that we know what the maximum is, we need to count the number of ways to actually attain it.
The subarray maximums are exactly N, N-1, \ldots, N - \left\lfloor \frac{N}{K}\right\rfloor + 1.
Let m = N - \left\lfloor \frac{N}{K}\right\rfloor + 1 be the minimum of these maximums.
Notice that m is the only value that might be the maximum of \lt K subarrays: everything else must be the maximum of all K subarrays containing it.
Specifically, m will be the maximum of ((N-K+1)\bmod K) subarrays (or K subarrays, if ((N-K+1)\bmod K) = 0), because there are N-K+1 subarrays of length K.
Let y denote the number of subarrays that have m as their maximum (as noted above, this is either ((N-K+1)\bmod K) or K).
Suppose these y subarrays are the ones starting at indices i, i+1, \ldots, i+y-1.
Then,
- m should be present in all these subarrays.
In other words, m should lie somewhere in the range [i+y-1, i+K-1], since it can’t be to the right of the leftmost subarray (which starts at i and so ends at i+K-1), and also can’t be to the left of the rightmost subarray (which starts at i+y-1).
Any one of these positions can be freely chosen. - Index i-1 must contain one of the elements larger than m; since that’s the only possible way for the subarray starting there to have its maximum be large (remember that by our choice, m isn’t allowed to be its maximum).
- As noted earlier, this element placed at index i-1 has to be the maximum of all K subarrays containing it.
So, the next ‘large’ element should be placed at index i-1-K, then by the same logic at i-1-2K, and so on. - The leftmost large element should then appear at index K, since that’s the only way for it to be the maximum of K subarrays (if it appeared to the left of K, there would be less than K subarrays containing it).
- As noted earlier, this element placed at index i-1 has to be the maximum of all K subarrays containing it.
- Similarly, to the right, index i+y-1+K should contain a large element, then i+y-1+2K, then i+y-1+3K, and so on.
With this in mind, let’s try to compute the number of permutations, with this fixed i.
- m can be placed anywhere between i+y-1 and i+K-1; which gives us K-y+1 choices in total.
- The positions of the other maximums are fixed, but at each position any of them can be placed.
There are (N-m) such positions (one for each element larger than m), and so (N-m)! ways to arrange the maximums there. - That leaves the (m-1) ‘small’ elements, that aren’t maximums of any subarray.
These can be arranged in any order, for (m-1)! ways.
So, for a fixed i, the number of arrangements is
which is easily found in \mathcal{O}(1) with precomputed factorials.
Further, there aren’t even too many choices for i.
In particular, recall that the leftmost maximum should be at position K (if m isn’t the leftmost, of course), meaning we must have i - 1 - xK = K for some integer x (we also need space for y subarrays of size K starting from i, of course; which just gives an upper bound on i).
This means the only choices of i are K+1, 2K+1, 3K+1, \ldots.
If m is the leftmost of the maximums, similar analysis will tell you that i = 1 is the only possible choice, so more generally, the choices for i are all integers of the form xK + 1 for x\geq 0.
There are only about \frac{N}{K} such integers i, so simply fixing K and bruteforcing them all gives a complexity of \mathcal{O}(\frac{N}{1} + \frac{N}{2} + \ldots + \frac{N}{N}) = \mathcal{O}(N\log N), which is fast enough.
You can improve this further to \mathcal{O}(N) by noticing that the value for a fixed i is in fact independent of i, so it’s enough to compute it for a single i and then multiply by their count.
This simplifies the answer for N and K to just
TIME COMPLEXITY:
\mathcal{O}(N) or \mathcal{O}(N\log N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int facN = 1e6 + 5;
const int mod = 1e9 + 7; // 998244353
int ff[facN], iff[facN];
bool facinit = false;
int power(int x, int y){
if (y == 0) return 1;
int v = power(x, y / 2);
v = 1LL * v * v % mod;
if (y & 1) return 1LL * v * x % mod;
else return v;
}
void factorialinit(){
facinit = true;
ff[0] = iff[0] = 1;
for (int i = 1; i < facN; i++){
ff[i] = 1LL * ff[i - 1] * i % mod;
}
iff[facN - 1] = power(ff[facN - 1], mod - 2);
for (int i = facN - 2; i >= 1; i--){
iff[i] = 1LL * iff[i + 1] * (i + 1) % mod;
}
}
int C(int n, int r){
if (!facinit) factorialinit();
if (n == r) return 1;
if (r < 0 || r > n) return 0;
return 1LL * ff[n] * iff[r] % mod * iff[n - r] % mod;
}
int P(int n, int r){
if (!facinit) factorialinit();
assert(0 <= r && r <= n);
return 1LL * ff[n] * iff[n - r] % mod;
}
int Solutions(int n, int r){
//solutions to x1 + ... + xn = r
//xi >= 0
return C(n + r - 1, n - 1);
}
void Solve()
{
int n; cin >> n;
for (int k = 1; k <= n; k++){
int m = n - k + 1;
int ans;
if (m % k == 0){
ans = ff[m / k] * ff[n - (m / k)] % mod;
} else {
// m / k things + 1 extra
ans = ff[m / k] * ff[n - (m / k) - 1] % mod * (m / k + 1) % mod * (k + 1 - (m % k)) % mod;
}
cout << ans << " \n"[k == n];
}
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
factorialinit();
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
constexpr int mod = (int)1e9 + 7;
int main() {
// your code goes here
int T; cin >> T;
while(T--) {
int N; cin >> N;
vector<long long> F(N + 1);
F[0] = 1;
for(int i = 1 ; i <= N ; ++i) F[i] = F[i - 1] * i % mod;
for(int k = 1 ; k <= N ; ++k) {
cout << F[N / k] * (k - N % k) % mod * F[N - N / k] % mod << " ";
}
cout << '\n';
}
}
Editorialist's code (Python)
mod = 10**9 + 7
N = 5*10**5 + 10
fac = [1]*N
for i in range(1, N): fac[i] = fac[i-1] * i % mod
for _ in range(int(input())):
n = int(input())
a = []
for k in range(1, n+1):
ans = 0
maxs = n//k
pos = 1
while pos <= n:
if pos+k > n+1: break
choices = k - n%k
ways = choices * fac[n - maxs] % mod * fac[maxs - 1] % mod
ans += ways
pos += k
a.append(ans % mod)
print(*a)