# Educational codeforces round 113 C. July meeting

https://codeforces.com/contest/1569/problem/C

#### Meaning:

n numbers. Every time it passes through a number, it will be - 1. If no number is continuously reduced twice when all numbers are reduced, such a sequence is called a good sequence. Find the number of all good sequences. The answer is mod998244353

#### Solution:

We can find that no matter what n is, we only look at the last two numbers in the end, and the remaining two numbers must be the largest number and the next largest number

Therefore, we can discuss it in the following three situations:

1. Maximum number = secondary maximum number

It has nothing to do with position. All arranged sequences are good sequences. The answer is n!

2. Maximum number > = secondary maximum number + 2

All sequences are not good sequences, and the answer is 0

3. There is only one maximum number, and the difference between the next largest number and the maximum number is 1

Through observation, we can find that at least one submaximal number is a good sequence if it is on the right of the maximum number, so the answer can be the case where the submaximal numbers are all on the left of the maximum number minus the full arrangement

The number of schemes with the next largest number of cycles to the left of the maximum can be calculated by enumerating the positions of the maximum:

We have cnt sub large numbers, then the maximum number can be placed at the position of n~cnt+1. Let the position of the maximum number be i, the space on the left of the maximum number is i-1, and the space on the right is n- i. the sub large number can only be placed at the position on the left, so there are ( c n t i − 1 ) \binom{cnt}{i-1} (i − 1 CNT) method. Now CNT sub large numbers and a maximum number have been put, so there are still n-cnt-1 numbers left. The remaining numbers can be put at will, so it is ( n − c n t − 1 ) ! (n-cnt-1)! (n−cnt−1)! Release method

( n − c n t − 1 ) ! ∗ ( c n t i − 1 ) (n-cnt-1)!*\binom{cnt}{i-1} (n−cnt−1)! * (I − 1cnt) is the illegal scheme number when the maximum number is placed at the i-th position. Enumerate I from n~cnt+1 and subtract it successively

#### code:

```#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>

#pragma GCC optimize(2)
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N = 2e5 + 5;
const int M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;

ll qpow(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1)res = res * a % mod;
a = (a * a) % mod;
b >>= 1;
}
return res;
}

int n, m, t;
ll a[N];
ll pre[N];//pre[i]=1*2*...*i
ll A(ll nn, ll mm) {
return pre[nn] * qpow(pre[nn - mm], mod - 2) % mod;
}

void solve() {
cin >> n;
ll maxx = -1;

for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n);
if (a[n - 1] >= a[n - 2] + 2)cout << 0 << '\n';
else if (a[n - 1] == a[n - 2])cout << pre[n] << '\n';
else {
int cnt = 0;
for (int i = 0; i < n; i++) {
if (a[i] == a[n - 2])cnt++;//The maximum value cannot be on the rightmost side of all sub maximum values
}
ll ans = pre[n];
for (int i = n; i >= cnt + 1; i--) { //i is the location of the maximum value. Enumeration i is located in a scheme number that is not a good sequence
ll res = (A(i - 1, cnt) * pre[n - cnt - 1]) % mod;
//cout<<res<<'\n';
ans = (ans - res + mod) % mod;
}
cout << ans % mod << '\n';

}

}

int main() {
//ios::sync_with_stdio(false);
pre = 1;

for (int i = 1; i <= 2e5; i++) {
pre[i] = (pre[i - 1] * i) % mod;
}
while (t--) {
solve();
}

return 0;
}

char ch = getchar();
ll p = 1, data = 0;
while (ch < '0' || ch > '9') {
if (ch == '-')p = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
data = data * 10 + (ch ^ 48);
ch = getchar();
}
return p * data;
}
```

Keywords: C++ Algorithm acm

Added by EdN on Thu, 09 Sep 2021 23:02:19 +0300