HDU6333 /// 莫队+组合数
发布时间:2020-12-14 05:13:48 所属栏目:大数据 来源:网络整理
导读:题目大意: 给定n m 在n个数中最多选择m个的所有方案 ? 题解:https://blog.csdn.net/qq_36300700/article/details/81385244 #include bits/stdc++.h using namespace std; #define INF 0x3f3f3f3f #define LL long long const int mod=1e9+ 7 ; const int N
题目大意: 给定n m 在n个数中最多选择m个的所有方案 ? 题解:https://blog.csdn.net/qq_36300700/article/details/81385244 #include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f #define LL long long const int mod=1e9+7; const int N=1e5+5; /********组合数模板*********/ LL pow_mod(LL a,LL b) { LL res = 1LL; a %= mod; while(b){ if(b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; } LL inv(LL a) { return pow_mod(a,mod-2); } LL F[N],Finv[N];//F是阶乘,Finv是逆元的阶乘 void init() { F[0] = Finv[0] = 1LL; for(int i = 1; i < N; i ++){ F[i] = F[i-1] * 1LL * (LL)i % mod; Finv[i] = Finv[i-1] * 1LL * inv(i) % mod; } } // O(n)预处理 LL C(LL n,LL m) { if(m < 0 || m > n) return 0; return F[n] * 1LL * Finv[n - m] % mod * Finv[m] % mod; } // O(1)获得组合数C(n,m) /**************************/ LL res[N]; /********莫队*********/ int len; struct Q { LL n,m; int block,id; bool operator <(const Q& q)const { if(block==q.block) return n<q.n; return block<q.block; } }q[N]; void Mo() { LL L=0,R=0,ans=1LL; for(int i=0;i<t;i++) { LL l=q[i].n,r=q[i].m; while(L>l) ans=((ans+C(L-1LL,R))%mod*Finv[2])%mod,L--; while(L<l) ans=(2*ans%mod-C(L,R)+mod)%mod,L++; while(R<r) ans=(ans+C(L,R+1))%mod,R++; while(R>r) ans=(ans-C(L,R--; res[q[i].id]=ans; } } /**************************/ int main() { init(); len=sqrt(N); int t; scanf("%d",&t); for(int i=0;i<t;i++) { scanf("%lld%lld",&q[i].n,&q[i].m); q[i].block=q[i].m/len; q[i].id=i; } sort(q,q+t); Mo(); for(int i=0;i<t;i++) printf("%lldn",res[i]); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |