【HDU 5145】 NPY and girls（组合+莫队）NPY and girls

95 阅读 0 评论 63 点赞

我是靠谱客的博主温婉丝袜，最近开发中收集的这篇文章主要介绍【HDU 5145】 NPY and girls（组合+莫队）NPY and girls，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

【HDU 5145】 NPY and girls（组合+莫队）

NPY and girls

Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 593 Accepted Submission(s): 179

Problem Description

NPY's girlfriend blew him out!His honey doesn't love him any more!However, he has so many girlfriend candidates.Because there are too many girls and for the convenience of management, NPY numbered the girls from 1 to n.These girls are in different classes(some girls may be in the same class).And the i-th girl is in class ai.NPY wants to visit his girls frequently.Each time he visits some girls numbered consecutively from L to R in some order. He can only visit one girl every time he goes into a classroom,otherwise the girls may fight with each other(-_-!).And he can visit the class in any order.
Here comes the problem,(NPY doesn't want to learn how to use excavator),he wonders how many different ways there can be in which he can visit his girls.The different ways are different means he visits these classrooms in different order.

Input

The first line contains the number of test cases

T(1≤T≤10) .
For each test case,there are two integers

n,m(0<n,m≤30000) in the first line.N is the number of girls,and M is the number of times that NPY want to visit his girls.
The following single line contains N integers,

a1,a2,a3,…,an , which indicates the class number of each girl.

(0<ai≤30000)
The following m lines,each line contains two integers

l,r(1≤l≤r≤n) ,which indicates the interval NPY wants to visit.

Output

For each visit,print how many ways can NPY visit his girls.Because the ans may be too large,print the ans mod 1000000007.

Sample Input

Sample Output


3
12
1

Source

BestCoder Round #22

Recommend

heyang

题目大意：T组输入

每组两个数 n m分别表示人数n和询问次数m

之后n个数表示n个女孩所在教室

对于m次询问每次一个[L,R]（1 <= L <= R <= n）问为了访问到每个女孩访问教室的方案有几种（会出现几个女孩在一个教室的情况但每次访问教室只能找一个女孩同一个编号的教室是相同的）

对于单组询问[L,R] 假设有n中班级每个班级有c个女生总共m个女生那么答案就是C(m,c1)*C(m-c1,c2)*C(m-c1-c2,c3)*....*C(cn,cn)

但如果每次都暴力的进行统计然后求组合数果果的会超时

这样就要用莫队把区间n进行分块分成n/sqrt(n)份进行分块排序

然后按分好的顺序进行区间的扩大或缩小这样可以发现对组合数的求解也可以在区间转换的过程中进行

因为C(m+1,n+1) = C(m,n)*(m+1/n+1)

同样的 C(m,n) = C(m+1,n+1)*(n+1/m+1) （对于缩小的过程而言）

这样由于n和m的范围都在30000之内而且要求最后对一个大素数取余可以用费马小定理快速求出范围内所有数的逆元

然后就像上面说的对区间进行转换然后离线处理存储答案最后输出即可记得答案要存在排序前的位置中。。。因为这个WA找了好久错误=.=

代码如下：

#include <iostream>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <list>
#include <algorithm>
#include <map>
#include <set>
#define LL long long
#define Pr pair<int,int>
#define fread() freopen("in.in","r",stdin)
#define fwrite() freopen("out.out","w",stdout)
using namespace std;
const int INF = 0x3f3f3f3f;
const int msz = 10000;
const LL mod = 1e9+7;
const double eps = 1e-8;
LL pow_m(LL a,LL b)
{
LL ans = 1;
while(b)
{
if(b&1) ans = (ans*a)%mod;
b >>= 1;
a = (a*a)%mod;
}
return ans;
}
LL Inv(LL a)
{
return pow_m(a,mod-2);
}
int per;
struct Range
{
int l,r,id;
bool operator < (const struct Range a)const
{
return l/per == a.l/per? r < a.r: l/per < a.l/per;
}
};
Range rg[30030];
LL ans[30030];
LL inv[30030];
int cla[30030];
int cnt[30030];
int main()
{
//fread();
//fwrite();
for(int i = 1; i <= 30000; ++i)
inv[i] = Inv(i);
int t,n,q;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&q);
per = sqrt(n*1.0);
for(int i = 1; i <= n; ++i)
scanf("%d",&cla[i]);
for(int i = 0; i < q; ++i)
{
scanf("%d%d",&rg[i].l,&rg[i].r);
rg[i].id = i;
}
sort(rg,rg+q);
int l = 1, r = 0;
LL tmp = 1;
memset(cnt,0,sizeof(cnt));
for(int i = 0; i < q; ++i)
{
while(r < rg[i].r)
{
++r;
cnt[cla[r]]++;
tmp = tmp*(r-l+1)%mod*inv[cnt[cla[r]]]%mod;
}
while(l > rg[i].l)
{
--l;
cnt[cla[l]]++;
tmp = tmp*(r-l+1)%mod*inv[cnt[cla[l]]]%mod;
}
while(r > rg[i].r)
{
tmp = tmp*cnt[cla[r]]%mod*inv[r-l+1]%mod;
cnt[cla[r]]--;
--r;
}
while(l < rg[i].l)
{
tmp = tmp*cnt[cla[l]]%mod*inv[r-l+1]%mod;
cnt[cla[l]]--;
++l;
}
ans[rg[i].id] = tmp;
}
for(int i = 0; i < q; ++i)
printf("%I64dn",ans[i]);
}
return 0;
}