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

NPY and girls

2
4 2
1 2 1 3
1 3
1 4
1 1
1
1 1

3
12
1

题目大意：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("%I64d\n",ans[i]);

	}

	return 0;
}

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

原文：http://blog.csdn.net/challengerrumble/article/details/50731052