新站网站推广公司,wordpress后台登录,建筑设计软件哪个好用,个人网站建设论文题意#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
