Description
给你一个序列s，你把这个序列的所有不同排列按字典序排列后，求s的排名mod m
Input
序列的长度$n < 300000,m$
$n$个数，代表序列s
Output
排名mod m
Sample Input
4 1000
2 1 10 2
Sample Output
5
HINT
All the permutations smaller (with respect to lexicographic order) than the one given are: (1,2,2,10), (1,2,10,2), (1,10,2,2) and (2,1,2,10). $2 \leq m \leq 10^9$, $1 \leq S_i \leq 300000$
题解
逐位考虑
考虑前$i-1$位与这个数列相等， 第$i$位比他小的数量
设有$g[i]$个数比他这一位小，那么答案为$g[i]*\frac{F[n - 1]}{\prod_{j = 1}^{n}{F[w[i]]}}$
其中$F[i]$位$i$的阶乘,$W[i]$为排除了前面已经确定的数后$i$的数量
这样就可以算出答案了
然而我们发现模数可能不是质数，那怎么办呢?
我们可以把他质因数分解，将模数拆成$p^k$相乘的形式
对于每一个$p^k$求模他的结果然后使用$CRT$合并
可是阶乘如果是$p^k$的倍数就会得$0$, 我们可以将阶乘拆成$a*p^b$的形式
可以实现乘法与除法。
然后解决了。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int MAXN = 300005;
long long a[MAXN], b[MAXN], c[MAXN], g[MAXN];
int Sum[MAXN], n, m;
long long B, P, PhiP, K;
long long pow_mod(long long a, int b, long long MP)
{
long long ans = 1;
while (b)
{
if (b & 1) ans = ans * a % MP;
b >>= 1;
a = a * a % MP;
}
return ans;
}
long long Inv(long long x)
{
return pow_mod(x, PhiP - 1, P);
}
struct Num
{
long long a, b;
Num(){a = 0, b = 0; }
Num(int _a)
{
a = _a;
while (a % B == 0)
a /= B, b++;
}
Num(long long _a, long long _b): a(_a), b(_b) {}
Num operator * (const Num &c) { return Num(a * c.a % P, b + c.b); }
Num operator / (const Num &c) { return Num(a * Inv(c.a) % P, b - c.b); }
long long val()
{
if (!a || b >= K) return 0;
long long x = a, k = b, c = B;
while (k)
{
if (k & 1) x = x * c % P;
k >>= 1;
c = c * c % P;
}
return x;
}
void Set(int x)
{
a = x, b = 0;
while (a % B == 0)
a /= B, b++;
}
}F[MAXN];
#define lowbit(_) ((_) & (-_))
void A(int x, int c)
{
for (int i = x; i <= n; i += lowbit(i))
Sum[i] += c;
}
int Q(int x)
{
int ans = 0;
for (int i = x; i >= 1; i -= lowbit(i))
ans += Sum[i];
return ans;
}
int cnt;
long long ans[5000], Mp[5000], Phi[5000];
void Solve()
{
cnt++;
Mp[cnt] = P, Phi[cnt] = PhiP;
F[0].Set(1);
for (int i = 1; i <= n; i++) F[i].Set(i);
for (int i = 1; i <= n; i++) F[i] = F[i] * F[i - 1];
for (int i = 1; i <= n; i++) c[i] = 0;
for (int i = 1; i <= n; i++) c[a[i]]++;
Num t(1, 0), tmp;
for (int i = 1; i <= n; i++) t = t * F[c[i]];
for (int i = 1; i <= n; i++)
{
if (g[i]) tmp.Set(g[i]), ans[cnt] = (ans[cnt] + (tmp * F[n - i] / t).val()) % P;
t = t / F[c[a[i]]] * F[c[a[i]] - 1];
c[a[i]]--;
}
}
void Divide(int x)
{
for (int i = 2; i * i <= x; i++)
if (x % i == 0)
{
B = i, P = 1, PhiP = 1, K = 0;
while (x % i == 0)
P *= i, PhiP *= i, K++, x /= i;
PhiP /= i, PhiP *= i - 1;
Solve();
}
if (x != 1)
{
B = x, P = x, PhiP = x - 1, K = 1;
Solve();
}
}
long long CRT(long long *a, long long *b, int n)
{
long long N = 1, Ni, now, ans = 0;
for (int i = 1; i <= n; i++) N *= a[i];
for (int i = 1; i <= n; i++)
{
Ni = N / a[i];
now = pow_mod(Ni, Phi[i] - 1, a[i]);
ans = (ans + (b[i] * now % N) * Ni % N) % N;
}
return ans;
}
int main()
{
n = read(), m = read();
for (int i = 1; i <= n; i++)
b[i] = a[i] = read();
sort(b + 1, b + n + 1);
int cnt = unique(b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= n; i++)
a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b;
for (int i = 1; i <= n; i++)
c[a[i]]++;
for (int i = 1; i <= n; i++) A(i, c[i]);
for (int i = 1; i <= n; i++)
g[i] = Q(a[i] - 1), A(a[i], -1);
Divide(m);
printf ("%lld\n", (CRT(Mp, ans, ::cnt) + 1) % m);
}