网站建设高效解决之道,网站容易出现的问题吗,高端企业网站价位,温州网站开发公司题意#xff1a; cases T(1≤T≤10) (0n,m≤30000) (0ai≤30000) n个数ai 表示n个女孩所在教室 m次询问 [L,R]#xff08;1 L R n#xff09; 问访问所有女孩的顺序方案数(进教室顺序)为多少(一次进教室只能访问一个人) 分析…题意 cases T(1≤T≤10) (0n,m≤30000) (0ai≤30000) n个数ai 表示n个女孩所在教室 m次询问 [L,R]1 L R n 问访问所有女孩的顺序方案数(进教室顺序)为多少(一次进教室只能访问一个人) 分析 莫队算法 排列数 一个区间内的方案数为 C(m,c1)*C(m-c1,c2)*C(m-c1-c2,c3)*....*C(cn,cn) 每次转移通过下式 C(m1,n1) C(m,n) * (m1/n1) C(m,n) C(m1,n1) * (n1/m1) 对于缩小的过程而言 因为需要对大素数取模除法就是乘上对应的乘法逆元故先用费马小定理 #include iostream
#include cstdio
#include cmath
#include algorithm
#include cstring
using namespace std;
const int MOD 1000000007;
const int MAXN 30005;
const int MAXM 30005;
struct Query
{int L,R,id;
}node[MAXM];
struct Ans
{long long a;
}ans[MAXM];
int a[MAXN],num[MAXN];
long long inv[MAXN];//乘法逆元
int t,n,m,unit;
void work()
{long long temp 1;memset(num,0,sizeof(num));int L 1 , R 0;for(int i 0; i m ; i){while(R node[i].R)//C(m1,n1) C(m,n)*(m1/n1){R;num[a[R]];temp temp * (R - L 1) % MOD * inv[num[a[R]]] % MOD;}while(R node[i].R)//C(m,n) C(m1,n1)*(n1/m1){temp temp * num[a[R]] % MOD * inv[R - L 1] % MOD;num[a[R]]--;R--;}while(L node[i].L)//C(m,n) C(m1,n1)*(n1/m1){temp temp * num[a[L]] % MOD * inv[R - L 1] % MOD;num[a[L]]--;L;}while(L node[i].L)//C(m1,n1) C(m,n)*(m1/n1){L--;num[a[L]];temp temp * (R - L 1) % MOD * inv[num[a[L]]] % MOD;}ans[node[i].id].a temp;}
}
bool cmp(Query a,Query b)
{if(a.L/unit ! b.L/unit) return a.L/unit b.L/unit;else return a.R b.R;
}
void Init()//femat
{inv[1] 1;for(int i 2; i MAXN; i) inv[i] inv[MOD % i] * (MOD - MOD / i) % MOD;
}
int main()
{Init();scanf(%d,t);while(t--){scanf(%d%d,n,m);for(int i 1; i n; i) scanf(%d,a[i]);for(int i 0; i m; i){scanf(%d%d,node[i].L,node[i].R);node[i].id i;}unit (int)sqrt(n);sort(node,nodem,cmp);work();for(int i 0; i m ;i)printf(%lld\n,ans[i].a);}
} 转载于:https://www.cnblogs.com/nicetomeetu/p/5709207.html
