[计数] 美团 CodeM 复赛 排列

#include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; typedef pair<int,int> abcd; typedef long long ll; #define read(x) scanf("%d",&(x)) const int P=1e9+7; inline ll Pow(ll a,int b){ ll ret=1; for (;b;b>>=1,a=a*a%P) if (b&1) ret=ret*a%P; return ret; } inline ll Inv(ll a){ return Pow(a,P-2); } const int N=100005; int n; int a[N],b[N],f[N]; int pos[N]; int c[N],maxn; inline void add(int x,int r){ for (int i=x;i<=maxn;i+=i&-i) (c[i]+=r)%=P; } inline int sum(int x){ int ret=0; for (int i=x;i;i-=i&-i) (ret+=c[i])%=P; return ret; } inline int sum(int l,int r){ if (l>r) return 0; return (sum(r)+P-sum(l-1))%P; } int main(){ int x,y; freopen("t.in","r",stdin); freopen("t.out","w",stdout); ll fac=1; read(n); for (int i=1;i<=n;i++) read(x),read(y),a[x]=y,fac=fac*i%P,pos[y]=i; maxn=n; for (int i=n;i;i--) b[i]=sum(a[i],n),add(a[i],1),b[i]=Inv(b[i]); maxn=n+1; for (int i=1;i<=n;i++) c[i]=0; add(0+1,Inv(n)); for (int i=1;i<=n;i++){ ll ret=sum(0+1,a[i]-1+1); if (!b[i]) f[pos[a[i]]]=ret*fac%P; else add(a[i]+1,ret*b[i]%P); } for (int i=1;i<=n;i++) printf("%d\n",f[i]); return 0; }