BZOJ1129 [POI2008]Per - NekoMio's Blog

Description#

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

Input#

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

Output#

排名mod m

Sample Input#

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
#include <cstdio>
2
#include <cstring>
3
#include <algorithm>
4
using namespace std;
5
inline int read()
6
{
7
    int x=0,f=1;char ch=getchar();
8
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
9
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
10
    return x*f;
11
}
12
const int MAXN = 300005;
13
long long a[MAXN], b[MAXN], c[MAXN], g[MAXN];
14
int Sum[MAXN], n, m;
15
long long B, P, PhiP, K;
16
long long pow_mod(long long a, int b, long long MP)
17
{
18
    long long ans = 1;
19
    while (b)
20
    {
21
        if (b & 1) ans = ans * a % MP;
22
        b >>= 1;
23
        a = a * a % MP;
24
    }
25
    return ans;
26
}
27
long long Inv(long long x)
28
{
29
    return pow_mod(x, PhiP - 1, P);
30
}
31
struct Num
32
{
33
    long long a, b;
34
    Num(){a = 0, b = 0; }
35
    Num(int _a)
36
    {
37
        a = _a;
38
        while (a % B == 0)
39
            a /= B, b++;
40
    }
41
    Num(long long _a, long long _b): a(_a), b(_b) {}
42
    Num operator * (const Num &c) { return Num(a * c.a % P, b + c.b); }
43
    Num operator / (const Num &c) { return Num(a * Inv(c.a) % P, b - c.b); }
44
    long long val()
45
    {
46
        if (!a || b >= K) return 0;
47
        long long x = a, k = b, c = B;
48
        while (k)
49
        {
50
            if (k & 1) x = x * c % P;
51
            k >>= 1;
52
            c = c * c % P;
53
        }
54
        return x;
55
    }
56
    void Set(int x)
57
    {
58
        a = x, b = 0;
59
        while (a % B == 0)
60
            a /= B, b++;
61
    }
62
}F[MAXN];
63
#define lowbit(_) ((_) & (-_))
64
void A(int x, int c)
65
{
66
    for (int i = x; i <= n; i += lowbit(i))
67
        Sum[i] += c;
68
}
69
int Q(int x)
70
{
71
    int ans = 0;
72
    for (int i = x; i >= 1; i -= lowbit(i))
73
        ans += Sum[i];
74
    return ans;
75
}
76
int cnt;
77
long long ans[5000], Mp[5000], Phi[5000];
78
void Solve()
79
{
80
    cnt++;
81
    Mp[cnt] = P, Phi[cnt] = PhiP;
82
    F[0].Set(1);
83
    for (int i = 1; i <= n; i++) F[i].Set(i);
84
    for (int i = 1; i <= n; i++) F[i] = F[i] * F[i - 1];
85
    for (int i = 1; i <= n; i++) c[i] = 0;
86
    for (int i = 1; i <= n; i++) c[a[i]]++;
87
    Num t(1, 0), tmp;
88
    for (int i = 1; i <= n; i++) t = t * F[c[i]];
89
    for (int i = 1; i <= n; i++)
90
    {
91
        if (g[i]) tmp.Set(g[i]), ans[cnt] = (ans[cnt] + (tmp * F[n - i] / t).val()) % P;
92
        t = t / F[c[a[i]]] * F[c[a[i]] - 1];
93
        c[a[i]]--;
94
    }
95
}
96
void Divide(int x)
97
{
98
    for (int i = 2; i * i <= x; i++)
99
        if (x % i == 0)
100
        {
101
            B = i, P = 1, PhiP = 1, K = 0;
102
            while (x % i == 0)
103
                P *= i, PhiP *= i, K++, x /= i;
104
            PhiP /= i, PhiP *= i - 1;
105
            Solve();
106
        }
107
    if (x != 1)
108
    {
109
        B = x, P = x, PhiP = x - 1, K = 1;
110
        Solve();
111
    }
112
}
113
long long CRT(long long *a, long long *b, int n)
114
{
115
    long long N = 1, Ni, now, ans = 0;
116
    for (int i = 1; i <= n; i++) N *= a[i];
117
    for (int i = 1; i <= n; i++)
118
    {
119
        Ni = N / a[i];
120
        now = pow_mod(Ni, Phi[i] - 1, a[i]);
121
        ans = (ans + (b[i] * now % N) * Ni % N) % N;
122
    }
123
    return ans;
124
}
125
int main()
126
{
127
    n = read(), m = read();
128
    for (int i = 1; i <= n; i++)
129
        b[i] = a[i] = read();
130
    sort(b + 1, b + n + 1);
131
    int cnt = unique(b + 1, b + n + 1) - b - 1;
132
    for (int i = 1; i <= n; i++)
133
        a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b;
134
    for (int i = 1; i <= n; i++)
135
        c[a[i]]++;
136
    for (int i = 1; i <= n; i++) A(i, c[i]);
137
    for (int i = 1; i <= n; i++)
138
        g[i] = Q(a[i] - 1), A(a[i], -1);
139
    Divide(m);
140
    printf ("%lld\n", (CRT(Mp, ans, ::cnt) + 1) % m);
141
}