分析

我们对于一个节点 考虑，如果有一个点 两维都大于 ，那么这个节点肯定不可能作为结尾。因为考虑一下，如果排列先出现 ，那么这个两维都是单调不降的，所以不可能转移到 ，反之，如果先出现 ，它一定保持不住结尾，最后整个图构成了一个有向无环图，每一个节点可以等概率转移到后置节点。那么一个节点对于它后面节点贡献就为，令考虑前 个，当前节点为结尾的概率 。那么它的贡献的计算 。因为它的贡献要被后面的节点等概率转移，所以 。那么这个就是个二维偏序的问题，考虑树状数组优化。先求出 。然后由小到大枚举 就好了，最后还要乘以所有方案数。时间复杂度为 。

代码

#include<bits/stdc++.h> 
using namespace std;
#define LL long long
LL read() {
    LL x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f=1;ch=getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
const LL mod = 1e9 + 7,N = 1e6 + 1000;
LL X[N],Y[N],inv[N],f[N],t[N],num[N],n;
void add(LL x,LL y) {
    for(LL i = x;i <= n;i+=i&-i) t[i] = (t[i] + y) % mod;
}
LL ask(LL x) {
    LL tot = 0;
    for(LL i = x;i;i -= i&-i) tot = (tot + t[i] + mod) % mod;
    return tot;
}
int main() {
    n = read();
    for(int i = 1;i <= n;i++) {
        int x = read();X[i] = x;Y[x] = read(); 
    }
    inv[0] = inv[1] = 1;
    for(int i = 2;i <= n;i++) inv[i] = (mod - (mod/i) * inv[mod % i] % mod + mod) % mod;
    for(int i = n;i >= 1;i--) {
        num[i] = n - i - ask(Y[i]);add(Y[i],1);
    }
    LL fac = 1;
    for(int i = 1;i < n;i++) fac = fac * i % mod;
    memset(t ,0 ,sizeof(t));
    add(1,1);
    for(int i = 1;i <= n;i++) {
        f[i] = inv[num[i]] * (ask(Y[i])) % mod;
        add(Y[i],f[i]);
    }
    for(int i = 1;i <= n;i++) {
        int id = X[i];
        if(num[id] == 0) printf("%lld\n",f[id] * fac % mod);
        else printf("0\n");
    }
}