NekoMio's Blog

美しいものが起こることを常に信じている

Description

给你一个序列s,你把这个序列的所有不同排列按字典序排列后,求s的排名mod m

Input

序列的长度$n < 300000,m$
$n$个数,代表序列s

Output

排名mod m

Sample Input

1
2
4 1000
2 1 10 2

Sample Output

1
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$的形式
可以实现乘法与除法。
然后解决了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#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);
}

本文作者 : NekoMio
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
本文链接 : https://www.nekomio.com/2018/03/24/139/

本文最后更新于 天前,文中所描述的信息可能已发生改变