禁书目录

C++(g++ 7.5.0) 解法, 执行用时: 871ms, 内存消耗: 34816K, 提交时间: 2022-08-22 09:52:25

#include <iostream>
#include <algorithm>
#include <map>

#define pr(x) std::cout << #x << ":" << x << std::endl

const int N = 1000007;

typedef long long ll;
typedef std::pair<int,int> pii;
const ll P = 998244353;
std::map<int,ll> mp;
ll mod_pow(ll x,ll n) {
    ll res = 1;
    while(n) {
        if(n & 1) res = res * x % P;
        x = x * x % P;
        n >>= 1;
    }
    return res;
}
int n;
pii ps[N];
int main() {
    std::ios::sync_with_stdio(false);
    std::cin >> n;
    for(int i = 1;i <= n;++i) {
        int a,b;
        std::cin >> a >> b;
        ps[i-1] = (pii){a,b};
    }
    std::sort(ps,ps+n);
    ll ans = 0;
    ll nn = 1;
    for(int i = 1;i <= n;++i) 
        nn = nn * i % P;
	int last = 0;
    for(int i = 0;i < n ;++i) {
        int pos = i;
        while(pos < n-1 && ps[pos] == ps[pos+1])
            ++pos;
        if(mp.count(ps[pos].second) == 0) 
            mp[ps[pos].second] = 1;
		if(ps[i].first != ps[last].first) last = i;
        ll big = n - last;
		mp[ps[pos].second] = mp[ps[pos].second] * (big - (pos - i + 1)) % P
            * mod_pow(big,P-2) % P;
        i = pos;
    }
    for(auto &p : mp) {
        ans = (ans + (nn * (1 + P - p.second) % P)) % P;
    }
    std::cout << ans << std::endl;
}

C++14(g++5.4) 解法, 执行用时: 343ms, 内存消耗: 11236K, 提交时间: 2018-10-12 22:41:53

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N=500010,Mo=998244353;
int a[N],b[N],id[N],f[N],inv[N];
inline int gi() {
    int x=0,o=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=='-'?o=-1:0,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return o*x;
}
int main() {
    int n,fac=1,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++) a[i]=gi(),b[i]=gi(),id[i]=i,fac=1LL*fac*i%Mo;
    sort(id+1,id+1+n,[](const int &x,const int &y) {return a[x]>a[y];});
    for(int i=n;i;i--) {
    if(a[id[i]]==a[id[i+1]]) f[id[i]]=f[id[i+1]];
    else f[id[i]]=i;
    }
    inv[1]=1;
    for(int i=2;i<=n;i++) inv[i]=1LL*(Mo-Mo/i)*inv[Mo%i]%Mo;
    stable_sort(id+1,id+1+n,[](const int &x,const int &y) {return b[x]<b[y];});
    for(int i=1;i<=n;i++) {
    int j=i;
    while(j<n&&b[id[j]]==b[id[j+1]]) ++j;
    int sum=fac;
    for(int k=i;k<=j;k++) {
        if(k>i&&a[id[k]]==a[id[k-1]]) f[id[k]]=f[id[k-1]]-1;
        sum=1LL*sum*inv[f[id[k]]]%Mo*(f[id[k]]-1)%Mo;
    }
    ans=(ans+fac)%Mo,ans=(ans+Mo-sum)%Mo,i=j;
    }
    cout<<ans;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 1062ms, 内存消耗: 33016K, 提交时间: 2019-06-12 20:17:07

#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>
const int mod=998244353;
const int M=1e6;
using namespace std;
int n,cnt,ans;
int h[M],inv[M],p[M];
map<int,int>mp;
struct node{int a,b;}f[M];
bool cmp(node i,node j) {
	return i.a==j.a?i.b<j.b:i.a>j.a;
}
int main() {
	scanf("%d",&n);
	for(int i=1,x,y;i<=n;i++) {
		scanf("%d%d",&x,&y);
		if(!mp[y]) mp[y]=++cnt;
		f[i]=(node){x,mp[y]};
	}
	sort(f+1,f+1+n,cmp);
	inv[1]=h[0]=h[1]=1;
	for(int i=2;i<=n;i++) {
		h[i]=1ll*h[i-1]*i%mod;
		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	}
	for(int i=1;i<=n;i++) p[i]=1;
	for(int i=1,j=1;i<=n;i=++j) {
		while(j<n&&f[i].a==f[j+1].a) ans=1ll*ans*j%mod,++j;
		ans=1ll*ans*j%mod;
		for(int k=i;k<=j;k++) ans=(ans+1ll*h[j-1]*p[f[k].b]%mod)%mod;
		for(int k=i,l=i;k<=j;k=++l) {
			while(l<j&&f[k].b==f[l+1].b) ++l;
			p[f[k].b]=1ll*p[f[k].b]*(j-l+k-1)%mod*inv[j]%mod;
		}
	}
	printf("%d\n",ans);
	return 0;
}

详情