首页 > 代码库 > HDU 5145 NPY and girls（莫队算法+乘法逆元）
HDU 5145 NPY and girls（莫队算法+乘法逆元）
【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5145
【题目大意】
给出一个数列，每次求一个区间数字的非重排列数量。答案对1e9+7取模。
【题解】
我们发现每次往里加入一个新的数字或者减去一个新的数字，前后的排列数目是可以通过乘除转移的，所以自然想到用莫队算法处理。因为答案要求取模，所以在用除法的时候要计算逆元。
【代码】
#include <cstdio>#include <algorithm>#include <cmath>#include <cstring>const int N=1000100;using namespace std;typedef long long LL;const LL mod=1e9+7;int pos[N],num[N],n,m,limit,i,l,r,S[N];LL rf[N]={0,1};LL ans,k,len;inline void init(){for(int i=2;i<N;i++)rf[i]=rf[mod%i]*(mod-mod/i)%mod;}struct Q{ int l,r,id;LL ans; friend bool operator < (const Q &a,const Q &b){ return pos[a.l]<pos[b.l]||(pos[a.l]==pos[b.l]&&a.r<b.r); }}ask[N];inline bool cmp(const Q &a,const Q &b){return a.id<b.id;}inline void read(int&a){ char ch;while(!((ch=getchar())>=‘0‘)&&(ch<=‘9‘)); a=ch-‘0‘;while(((ch=getchar())>=‘0‘)&&(ch<=‘9‘))a*=10,a+=ch-‘0‘;}inline void modify(int p,LL &ans,int add){ if(add>0)S[num[p]]++,ans=ans*(++len)%mod*rf[S[num[p]]]%mod; else ans=ans*S[num[p]]%mod*rf[len--]%mod,S[num[p]]--;}int T;int main(){ init(); read(T); while(T--){ read(n);read(m); limit=(int)sqrt(n+0.5); memset(S,0,sizeof(S)); for(i=1;i<=n;i++){read(num[i]);pos[i]=(i-1)/limit+1;} for(i=1;i<=m;i++){read(ask[i].l);read(ask[i].r);ask[i].id=i;} sort(ask+1,ask+m+1); ans=1; len=0; for(i=1,l=1,r=0;i<=m;i++){ while(r<ask[i].r)modify(++r,ans,1); while(r>ask[i].r)modify(r--,ans,-1); while(l<ask[i].l)modify(l++,ans,-1); while(l>ask[i].l)modify(--l,ans,1); ask[i].ans=ans; }sort(ask+1,ask+m+1,cmp); for(i=1;i<=m;i++)printf("%lld\n",ask[i].ans); }return 0;}
HDU 5145 NPY and girls（莫队算法+乘法逆元）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。