CodeForces - 1207D （组合数学）

题目链接：https://vjudge.net/problem/CodeForces-1207D

题意：

给出一个序列，每个点有两个值，定义坏的序列就是满足左键值，右键值都是单调不递减的。求出有多少个好的序列。

思路：

主要是两个方面：关键字之间的关系，出现重复关键字的关系。

关键字A，B产生坏的序列是求和的关系，主要是去除AB共同产生的坏的序列；重复关键子x的数量是y，产生的坏的序列的数量是fac[y]。

当时想的时候没考虑清楚一个问题：

两个键值顺序相同的序列会产生冲突

eg：1-5，2-6，3-7，4-8，这种情况，总结果要是fac[n] - （第一个关键字的重复值 + 第二个关键字的重复着 - 两个关键字共同的重复值）。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
typedef long long ll;
const ll mod = 998244353;
struct Node
{
int x,y;
}cur[N];
int num1[N] = {0},num2[N] = {0};
ll p[N] = {0};
bool cmp(Node a,Node b)
{
if(a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
int main(void)
{
int n,mx = 0;
p[0] = 1;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
p[i] = p[i-1] * i%mod;
scanf("%d%d",&cur[i].x,&cur[i].y);
num1[ cur[i].x ]++;
num2[ cur[i].y ]++;
mx = max(mx,max(cur[i].x,cur[i].y));
}
sort(cur+1,cur+1+n,cmp);
ll t1 = 1,t2 = 1;
for(int i=0;i<=mx;i++)
{
if(num1[i] > 1) t1 = t1*p[ num1[i] ]%mod;
if(num2[i] > 1) t2 = t2*p[ num2[i] ]%mod;
}
bool fg = false;
for(int i=1;i<n;i++)
if(cur[i].y > cur[i+1].y){
fg = true;break;
}
ll ans = ( (t1 + t2)%mod + mod)%mod;
if(fg == false)
{
ll tt = 1;
for(int i=1;i<=n;i++)
{
int cnt = 1;
while(i+1<=n && cur[i].x == cur[i+1].x && cur[i].y == cur[i+1].y) cnt++,i++;
if(cnt > 1)
{
tt = tt*p[cnt]%mod;
}
}
ans = ( (p[n] - ans + tt)%mod + mod)%mod;
}
else ans = (p[n] - ans+mod)%mod;
printf("%lldn",ans);
return 0;
}

最后

以上就是感性时光为你收集整理的CodeForces - 1207D （组合数学）的全部内容，希望文章能够帮你解决CodeForces - 1207D （组合数学）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。