C. Jury Meeting
题意
n个人,个人都有ai个事件要说,当轮到某个人的时候,如果他现在有需要说的事,那就给他的ai减1,如果没有需要说的了,就往下轮,直到所有人都说完了,这过程中不能同一个人说两次
思路
三种情况
1、当最大值的数存在两个的时候,结果为n!,任意排列
2、当最大值-1这个数不存在的时候 结果为0
3、当最大值与最大值-1都存在,符合答案的情况是最大值在至少一个次大值前面
怎么计算第三种情况?
让全部情况数即n! 减 最大值在最后的情况。
最大值和次大值以外的数的顺序无所谓,不需要考虑位置。
假设现在有次大值k个,根据插空原理可以产生k+1个空位,那么最大值排在最后一个空位的概率就是 1/(k+1),所以不合法的情况数量就是 n!/(k+1) 。最后总方案数就是 n! - n!/(k+1)。
图示:
代码
#include <iostream>
#include <cstring>
#include <set>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <sstream>
using namespace std;
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define int long longconst int mod = 998244353;
const int N = 1e5 + 10;
int a[N]; void solve()
{int n;cin >> n;vector<int> a(n);for(int &x : a) cin >> x;int mx = *max_element(a.begin(), a.end());int cmx = count(a.begin(), a.end(), mx);int k = count(a.begin(), a.end(), mx - 1);int ans = 1, sum = 1;for(int i = 1; i <= n; i ++){// n!ans = ans * i % mod;// 少一个(k+1) mx-1的数量+1if(i != k + 1) sum = sum * i % mod;}if(cmx == 1) ans = (ans - sum + mod) % mod;cout << ans << endl;
}signed main()
{int ________________________________________________________________________;cin >> ________________________________________________________________________;while (________________________________________________________________________--){solve();}
}
更多推荐
Meeting,Jury,Educational,Codeforces
发布评论