比赛题。懒得写crt而丢暴力。
问$n leq 300000$的数列的字典序，$mod m$，不保证$m$是质数，数列$leq 300000$，有重复。
虽然说这种强行套两个知识的题目很令人厌恶，但征服他们才是我们厌恶的资本。
首先$p_i$表示数列第$i$个数，$c_i$表示值为$i$有多少个，$t$表示所有数字的最大值，我们要求的是$1+sum_{i=1}^{n} sum_{j=1}^{p_i-1} frac{(n-i)!}{(c_j-1)! prod_{k=1}^{t}[k eq j]c_k!}$。
上下同乘$c_j$，得，等会！！！！！严肃注意，在这里同乘$c_j$，若$c_j=0$则会出现奇怪错误！！所以在式子转化的过程中千万记得，把条件写上去。在这卡了1.5h。
$sum_{i=1}^{n} frac{(n-i)!}{prod_{k=1}^{t}c_k!}sum_{j=1}^{p_i-1}c_j!(这坨东西不为0)$.
好的！由于$c$会变，后面那坨用树状数组解决，而那个分式需要对$m$取$mod$，不方便，就把$m$分解完，$m=sum_{i=1}^{k}a_i^{b_i}$，枚举每个$a_i^{b_i}$做膜数，用欧拉定理求逆元，把质因子$a_i$计指数单独拿出来算。最后用中国剩余定理合并。
1 //#include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 //#include<time.h> 6 //#include<complex> 7 #include<algorithm> 8 #include<stdlib.h> 9 using namespace std; 10 11 int n,mod; 12 #define maxn 300011 13 int cnt[maxn],pp[maxn],a[maxn]; 14 struct BIT 15 { 16 int a[maxn],n; 17 void clear(int m) {n=m;} 18 void add(int x,int v) {for (;x<=n;x+=x&-x) a[x]+=v;} 19 int query(int x) {int ans=0; for (;x;x-=x&-x) ans+=a[x]; return ans;} 20 }t; 21 22 int powmod(int a,int b,int mod) 23 { 24 // cout<<b<<endl; 25 int ans=1; 26 while (b) 27 { 28 if (b&1) ans=1ll*ans*a%mod; 29 a=1ll*a*a%mod; b>>=1; 30 } 31 return ans; 32 } 33 34 int mm[maxn],ci[maxn],phi[maxn],mi[maxn],num[maxn],ln; 35 void dec() 36 { 37 int tmp=mod; ln=0; 38 for (int i=2;1ll*i*i<=tmp;i++) if (tmp%i==0) 39 { 40 num[++ln]=i; mi[ln]=1; 41 while (tmp%i==0) tmp/=i,mi[ln]*=i; 42 } 43 if (tmp>1) num[++ln]=tmp,mi[ln]=tmp; 44 for (int i=1;i<=ln;i++) phi[i]=mi[i]-mi[i]/num[i]; 45 } 46 47 int xx[maxn]; 48 int china() 49 { 50 int ans=0; 51 for (int i=1;i<=ln;i++) 52 { 53 int w=mod/mi[i],ni=powmod(w,phi[i]-1,mi[i]); 54 ans=(ans+1ll*w*ni%mod*xx[i])%mod; 55 } 56 return ans; 57 } 58 59 int main() 60 { 61 scanf("%d%d",&n,&mod); int Max=0; 62 for (int i=1;i<=n;i++) scanf("%d",&a[i]),cnt[a[i]]++,Max=max(Max,a[i]); 63 t.clear(Max); 64 dec(); 65 for (int j=1;j<=ln;j++) 66 { 67 mm[j]=1; 68 for (int tmp=1;1ll*tmp*num[j]<=n;tmp*=num[j]) ci[j]+=n/(tmp*num[j]); 69 for (int i=1;i<=n;i++) 70 { 71 int tmp=i; while (tmp%num[j]==0) tmp/=num[j]; 72 mm[j]=1ll*mm[j]*tmp%mi[j]; 73 } 74 for (int i=1;i<=Max;i++) 75 { 76 for (int k=1;1ll*k*num[j]<=cnt[i];k*=num[j]) ci[j]-=cnt[i]/(k*num[j]); 77 for (int k=1;k<=cnt[i];k++) 78 { 79 int tmp=k; while (tmp%num[j]==0) tmp/=num[j]; 80 mm[j]=1ll*mm[j]*powmod(tmp,phi[j]-1,mi[j])%mi[j]; 81 } 82 } 83 } 84 for (int i=1;i<=Max;i++) if (cnt[i]) t.add(i,cnt[i]); 85 for (int i=1;i<=n;i++) 86 { 87 int nowt=t.query(a[i]-1); 88 for (int j=1;j<=ln;j++) 89 { 90 int tmp=n-i+1; 91 while (tmp%num[j]==0) ci[j]--,tmp/=num[j]; 92 mm[j]=1ll*mm[j]*powmod(tmp,phi[j]-1,mi[j])%mi[j]; 93 if (nowt) 94 { 95 tmp=nowt; 96 while (tmp%num[j]==0) ci[j]++,tmp/=num[j]; 97 xx[j]=(xx[j]+mm[j]*1ll*powmod(num[j],ci[j],mi[j])%mi[j]*tmp)%mi[j]; 98 tmp=nowt; 99 while (tmp%num[j]==0) ci[j]--,tmp/=num[j]; 100 } 101 tmp=cnt[a[i]]; 102 while (tmp%num[j]==0) ci[j]++,tmp/=num[j]; 103 mm[j]=1ll*mm[j]*tmp%mi[j]; 104 } 105 cnt[a[i]]--; t.add(a[i],-1); 106 } 107 printf("%d ",(china()+1)%mod); 108 return 0; 109 }