盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码

HDU 5145 NPY and girls(区间查询+莫队算法)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=5145

题意

有n个数,m个询问,每次询问区间[l,r]中数字全排列的个数

思路

首先区间全排列为:(r-l+1)! / (a1! a2! ……) 其中ai为每种数的个数。
假设已经知道当前区间[l,r]的值f, 那么[l,r+1]就是f
(r-l+2) / ai (其中ai为新加进来数的个数)。这里用莫队算法来进行维护

莫队算法可以用nsqrt(n)的复杂度解决一切离线不修改的区间查询问题 [从(l,r)->(l+1,r)的递推复杂度必须为O(1)]
算法参考:http://blog.csdn.net/huzecong/article/details/8576908
http://blog.csdn.net/bossup/article/details/39236275
莫队算法可以把区间当做二维的点,然后求出曼哈顿最小生成树,之后从起点dfs出答案。
但是上述代码比较复杂,另一种方式是把n分块,分成sqrt(n)块。然后把所有查询离线,然后先按照l属于的块号从小到大排序,如果两者在同一块,则按照r从小到大排序。之后遍历一遍得到答案

代码

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
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define INF 1 << 30
#define fi first
#define se second
#define debug puts("=====================");
using namespace std;
typedef long long ll;
const int N = 3e4 + 100;
const int mod = 1000000007;
int n, m, B;
int c[N], cnt[N], res[N];
struct node {
int l, r, id;
}a[N];
bool cmp(node s, node v) {
if (s.l / B == v.l / B) return s.r < v.r;
return s.l < v.l;
}
ll inv[N];
void init(int n) {
inv[0] = inv[1] = 1;
for (int i = 2; i <= n; i++) inv[i] = inv[mod % i] * (mod - mod / i) % mod;
}
int main () {
int t;
init(30000);
scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
scanf("%d", c + i);
cnt[c[i]] = 0;
}
for (int i = 0; i < m; i++) {
scanf("%d%d", &a[i].l, &a[i].r);
a[i].l--, a[i].r--;
a[i].id = i;
}
B = sqrt(n + 0.5);
sort(a, a + m, cmp);
int L = a[0].l, R = a[0].l - 1;
ll ans = 1;
for (int i = 0; i < m; i++) {
while(R < a[i].r) {
R++;
cnt[c[R]]++;
ans = ans * (R - L + 1) % mod;
ans = ans * inv[cnt[c[R]]] % mod;
}
while(R > a[i].r) {
ans = ans * inv[R - L + 1] % mod;
ans = ans * cnt[c[R]] % mod;
cnt[c[R]]--;
R--;
}
while(L > a[i].l) {
L--;
cnt[c[L]]++;
ans = ans * (R - L + 1) % mod;
ans = ans * inv[cnt[c[L]]] % mod;
}
while(L < a[i].l) {
ans = ans * inv[R - L + 1] % mod;
ans = ans * cnt[c[L]] % mod;
cnt[c[L]]--;
L++;
}
res[a[i].id] = ans;
}
for (int i = 0; i < m; i++) printf("%d\n", res[i]);
}
return 0;
}