HDU 6311 Harvest of Apples (组合数，莫队) _组合

相逢意气为君饮，系马高楼垂柳边。这篇文章主要讲述HDU 6311 Harvest of Apples (组合数，莫队)相关的知识，希望能为你提供帮助。
场上怎么都想不出来，看了标程想自闭。。。

#include < algorithm> #include < iostream> #include < cstdio> #include < vector> #include < cmath> using namespace std; #define N 100005 #define mod 1000000007 struct query{ int n,k,i; }Q[N]; bool cmp(const query& a,const query& b){ return a.n< b.n; } int reflect[N]; ///分块 vector< query> lis[2000]; int fac[N],inv[N]; int quick(int a,int b){ int odd = 1; while (b){ if(b& 1)odd = 1ll*odd*a%mod; a = 1ll*a*a%mod; b> > =1; } return odd; } const int mx = 100000; void deal(){ fac[0] = 1; for(int i = 1 ; i < = mx ; ++i){ fac[i] = 1ll*i*fac[i-1]%mod; } inv[mx] = quick(fac[mx],mod-2); for(int i = mx ; i ; --i){ inv[i-1] = 1ll*i*inv[i]%mod; } } int res[N]; int C(int n,int m){ return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod; } int main() { deal(); int cent = sqrt(mx); int cnt = 1; for (int i = 1; i < = mx; i += cent, ++cnt) { for (int j = i; j < = mx and j < = i + cent; ++j) { reflect[j] = cnt; } } int T; scanf("%d",& T); for(int i = 1 ; i < = T ; ++i){ scanf("%d %d",& Q[i].n,& Q[i].k); Q[i].i = i; lis[reflect[Q[i].k]].push_back(Q[i]); } for(int i = 1 ; i < = cnt ; ++i)if(!lis[i].empty()){ sort(lis[i].begin(),lis[i].end(),cmp); int val = 0,in = lis[i][0].n,ik = -1; for(auto & j : lis[i]){ while (in< j.n)val = (0ll + val + val + mod - C(in++,ik))%mod; while (ik< j.k)val = (val + C(in,++ik))%mod; while (ik> j.k)val = (val + mod - C(in,ik--))%mod; res[j.i] = val; } } for(int i = 1 ; i < = T ; ++i){ printf("%d ",res[i]); } }

【HDU 6311 Harvest of Apples (组合数，莫队)】标程太秀了，顶礼膜拜。