PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Combinatorics
PROBLEM:
You’re given a 2\times N grid, with both rows being permutations of [1, N].
You’re allowed to swap adjacent elements within the first row.
Define the score of the grid as the minimum number of adjacent swaps needed to allow for the following:
- It’s possible to start at (1, 1) and reach (2, N), while always moving a cell with value x to an adjacent cell with value either x or x+1.
Given only the second row of the grid, compute the sum of scores across all first rows.
EXPLANATION:
Let P denote the permutation of the first row, and Q denote the second row.
From the base version, we already know how to compute the answer for a single fixed grid:
- If Q_N \ne N, no solution exists.
- Otherwise, the positions where Q_i \ne i force P_{i-1} = i-1, P_i = i, P_{i+1} = i+1 to hold.
- Also P_1 = 1 must hold.
- These conditions were necessary and sufficient.
- This uniquely determines the final permutation, after which the swap count was found as just the number of inversions between the initial and final permutations.
We now need to adapt this to summing up across all choices of the first row.
First, if Q_N \ne N then no choice of P is valid, so we just print 0 immediately.
Otherwise, the indices where Q_i = i force certain values of P to be in their respective columns.
Let there be k such forced values.
Recall that the final permutation is to place all forced values in place, then arrange the unforced values from left to right in the remaining positions.
In particular, we observed that there would be no swaps between unforced elements.
Using this information, we can try to separately count swaps between forced elements, and between a forced and an unforced element.
Let’s deal with swaps between forced elements first.
Observe that we need to swap two forced elements if and only if they form an inversion.
The set of k forced values is always fixed, so we only need to sum up inversions among them across all permutations.
This is easy:
- There are \binom{k}{2} pairs of forced elements.
- For each pair, there’s a bijection between permutations that contain this pair as an inversion and permutations that don’t (just swap the values in the permutation.)
- Thus, for each pair, exactly half of all permutations contain it as an inversion.
Thus, the total number of inversions, summed up, simply equals
Next, we need to sum up the swaps between forced and unforced elements.
To do this, we need to understand exactly how many swaps occur between forced and unforced elements.
For each forced position i, define:
- x_i to be the number of unforced positions appearing before position i, in P.
- y_i to be the number of unforced positions appearing before value i, in P.
Then, we need exactly |x_i - y_i| swaps involving i and an unforced element.
Thus, for each forced position i, we only need to sum up the values of |x_i - y_i| across all permutations P.
This is not hard: observe that x_i is a constant that’s independent of P, which makes our work a lot easier.
If we fix a value of y_i, we need to count permutations where the value i appears after exactly y_i other unforced values.
This can be done as follows:
- First, pick N-k+1 positions in [1, N].
These will hold all unforced values, as well as i.
There are \binom{N}{N-k+1} ways to do this; since i is forced to be in the (y_i)-th position anyway. - Then, there are (N-k)! ways to order the unforced elements among their positions.
- There are also (k-1) ways to order the forced elements (other than i) among their positions.
Thus, the total number of permutations with this fixed value of y_i, equals
Observe that this is completely independent of both i and y_i itself.
Thus, for any y_i, this value is the contribution of |x_i - y_i| to the sum.
So, we end up just needing to find the sum of |x_i - y_i| across all 0 \le y_i \le N-k.
This is trivial to do with a bit of algebra; just split out the x_i \le y_i and x_i \gt y_i cases separately and it turns into summing up consecutive numbers.
This gives us a linear-time solution to this version of the problem.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 998244353;
const int N = 2e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
ll fact[N], ifact[N];
ll bexp(ll a, ll b) {
a %= MOD;
if (a == 0) return 0;
ll res = 1;
while (b) {
if (b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
ll invmod(ll a) {
return bexp(a, MOD - 2);
}
ll ncr(ll n, ll r) {
if (n < 0 or r < 0 or n < r) return 0;
return fact[n] * ifact[r] % MOD * ifact[n - r] % MOD;
}
ll npr(ll n, ll r) {
if (n < 0 or r < 0 or n < r) return 0;
return fact[n] * ifact[n - r] % MOD;
}
void precalc(ll n) {
fact[0] = 1;
rep1(i, n) fact[i] = fact[i - 1] * i % MOD;
ifact[n] = invmod(fact[n]);
rev(i, n - 1, 0) ifact[i] = ifact[i + 1] * (i + 1) % MOD;
}
void solve(int test_case){
ll n;
cin >> n;
vector<ll> b(n+5);
rep1(i,n) cin >> b[i];
if(b[n] != n){
cout << 0 << endl;
return;
}
vector<pll> segs;
vector<ll> c(n+5);
rep1(i,n){
if(b[i] == i){
if(!segs.empty() and segs.back().ss+1 == i){
segs.back().ss++;
}
else{
segs.pb({i,i});
}
}
else{
c[i] = i;
}
}
for(auto [l,r] : segs){
c[l] = l;
if(r != n) c[r] = r;
}
vector<bool> exists(n+5);
rep1(i,n){
if(c[i]){
exists[c[i]] = 1;
}
}
vector<ll> pref(n+5);
ll zeros = 0;
rep1(i,n){
if(!c[i]) zeros++;
else pref[c[i]] = zeros;
}
ll non_zeros = n-zeros;
ll inv_contrib = fact[non_zeros]*non_zeros%MOD*(non_zeros-1)%MOD*invmod(4)%MOD;
ll zeros_contrib = 0;
rep1(value,n){
if(!exists[value]) conts;
ll x = pref[value];
// y < x
zeros_contrib += x*(x+1)/2;
// y > x
ll mx = zeros-x;
zeros_contrib += mx*(mx+1)/2;
}
zeros_contrib %= MOD;
ll mul = ncr(n,zeros+1)*fact[n-zeros-1]%MOD*fact[zeros]%MOD;
zeros_contrib = zeros_contrib*mul%MOD;
inv_contrib = inv_contrib*ncr(n,zeros)%MOD*fact[zeros]%MOD;
ll ans = (inv_contrib+zeros_contrib)%MOD;
cout << ans << endl;
}
int main()
{
precalc(N-1);
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
cerr << "RUN SUCCESSFUL" << endl;
return 0;
}