Jury Meeting(思维/数论)

题目 题意：给定 n n n个人，每人手上有 a i a_i ai​个任务。给定一个排列顺序后，每个人轮流讲自己的任务，每次讲一个。当没有任务时，则轮空。问有多少种排列方式，使得不会出现某个人会连续讲任务的情况。 比如 a = { 1 , 2 } a=\{1,2\} a={1,2}，对于排列 { 1 , 2 } \{1,2\} {1,2}，会出现第二个人连续讲自己的任务的情况；而对于排列 { 2 , 1 } \{2,1\} {2,1}，则不会出现这种情况。 参考 思路：可以发现，会出现连续讲两次的人选，一定是手头任务最多的人。其次，当手头任务最多的人数有2人以上时，不会出现连续讲两次的人选，比如对于数组 { 3 , 3 , 3 } \{3,3,3\} {3,3,3}，这三个人无论怎么排列，起得作用都一样，讲完后都会有相应的人选来轮下去。 对于手头任务最多的人数只有1人（不妨叫做king）的情况，观察手头任务为mx-1的人数，假设有k人。则其他人数有 n − k − 1 n-k-1 n−k−1人，其余人可以随意排列，即 A n n − k − 1 = n ! ( k + 1 ) ! A_{n}^{n-k-1}=\frac{n!}{(k+1)!} Ann−k−1​=(k+1)!n!​，要使king最后会连续讲两次任务，他只能放在最后，其余k人，随意排列，即 A k k = k ! A_{k}^{k}=k! Akk​=k!。 所以答案为 n ! − A n n − k − 1 ∗ A k k = n ! − n ! k + 1 n!-A_{n}^{n-k-1}*A_{k}^{k}=n!-\frac{n!}{k+1} n!−Ann−k−1​∗Akk​=n!−k+1n!​

#include
using namespace std;
#define ll long long
const int maxn = 200010;
const int mod  = 998244353;

int n;
int a[maxn];
int p[maxn], inv[maxn];

/*
 * 0