根本不需要中国剩余定理就可以A掉!
看完题面你会惊人地发现这好像一个康托展开！（显然是不同的啦）
首先我们来看康托展开这个东西在数组为排列时怎么打
------->度娘
int cantor(int a[],int n){//cantor展开,n表示是n位的全排列，a[]表示全排列的数（用数组表示） int ans=0,sum=0; for(int i=1;i<n;i++){ for(int j=i+1;j<=n;j++) if(a[j]<a[i]) sum++; ans+=sum*factorial[n-i];//累积 sum=0;//计数器归零 } return ans+1; }对于每一个数算出贡献,贡献为后面出现的比它小的数（设w个即这一位本来还可以选的数）乘上后面数个数的阶乘
这个w显然可以用树状数组优化
由于后面的数会出现重复,所以我们对于那些重复的数（假设出现了k次）,他们会被枚举出\(k!\)种排列，我们要把它除掉
所以这个数\(a[i]\)的贡献为
\[w \cdot \frac{(n-i)!}{\Pi \ {cnt[j]!}}\]
\(cnt[j]\)表示i~n这一段中每个数 j 出现的个数
对于这个分母,显然不可以高精!我们会自然想到模逆元,但模逆元也是要求互质的!那怎么办?
把\(m\)的因数在答案中出现的提出来,不就互质了吗！（也就是在每次计算时把这些因子除掉,记录提出因子的个数）
由于对于上面的式子 \(\frac{(n-i)!}{\Pi \ {cnt[j]!}}\)
这个东西显然是个整数,(你可以像证明组合数是个整数一样证明它)，所以上面的因子个数-下面这些因子的个数显然是自然数,提出来后把剩下的答案乘出来，最后再把那些多出来的因子乘上去就行了
tips:因为模数不是质数,故不能用费马
(你可以看一下我丑陋的code)
typedef long long ll; #define reg register #define rep(a,b,c) for(int a=b,a##end=c;a<=a##end;++a) #define drep(a,b,c) for(int a=b,a##end=c;a>=a##end;--a) const int N=3e5+10; int n,m; void Exgcd(ll a,ll b,ll &x,ll &y){ if(b==0) { x=1,y=0; return ;} Exgcd(b,a%b,y,x); y-=a/b*x; } inline ll Inv(ll x,ll P){ ll a,b; Exgcd(x,P,a,b); return (a%P+P)%P; } int a[N]; struct BIT{ ll s[N]; void init(){ memset(s,0,sizeof s); } void Add(int p,int x){ while(p<N) s[p]+=x,p+=p&-p; } ll Que(int p){ int res=0; while(p) res+=s[p],p^=p&-p; return res; } }Bit; //树状数组用来求大于i小于a[i]的个数 int c[N],cc[N]; ll fac[N],fcnt,b[N],pq[N]; ll po[50][N]; int cnt[50]; //cnt记录m的每一个因数被提出来的个数 void Count(ll &x,int k){ rep(i,1,fcnt){ int p=fac[i]; while(x%p==0) { x/=p; cnt[i]+=k; } } } ll Get(){ ll res=1; rep(i,1,fcnt) (res*=po[i][min(cc[i],cnt[i])])%=m; return res; } ll Solve(){ ll ans=1,res=1; c[a[n]]=1,Bit.Add(a[n],1); drep(i,n-1,1){ ll t=n-i; Count(t,1);//计算(n-i)!要多乘上的值,也提出m的因数 (res*=t)%=m; t=++c[a[i]];//计算分子中变化的值,提出其中m的因数 //这两步保证了求逆元时一定是互质有解的 Count(t,-1); (res*=Inv(t,m))%=m; Bit.Add(a[i],1); t=Get();//计算提出因数的总乘积 (ans+=res*Bit.Que(a[i]-1)%m*t%m)%=m; //套入计算公式 } return ans; } int main(){ n=rd(),m=rd(); rep(i,1,n) a[i]=rd(); int tmp=m; for(int i=2;(i*i)<=tmp;i++) if(tmp%i==0){ fac[++fcnt]=i; po[fcnt][0]=1; rep(j,1,N-1) po[fcnt][j]=po[fcnt][j-1]*i%m,cc[fcnt]++; while(tmp%i==0) tmp/=i; } if(tmp>1) { fac[++fcnt]=tmp; po[fcnt][0]=1; rep(j,1,N-1) po[fcnt][j]=po[fcnt][j-1]*tmp%m,cc[fcnt]++; } //处理出m的因数,预处理次方 printf("%lld\n",Solve()); }转载于:https://www.cnblogs.com/chasedeath/p/11258762.html
相关资源：JAVA上百实例源码以及开源项目