本文主要是介绍hdu 6333 Harvest of Apples，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：点击打开链接
题意：给出T组n和m（1<=T<=1e5, 1<=m<=n<=1e5）。求
分析：
法一：S(l,r)=S(l,r+1)-C(l,r+1)
=S(l,r-1)+C(l,r);
=2*S(l-1,r)-C(l-1,r) （由杨辉三角得出，利用前缀和组合数性质）
=(S(l+1,r)+C(l,r))/2;
利用莫队离线处理，预处理一下，即可O(1)转移。
法二：利用杨辉三角的性质，分段打表，参考点击打开链接。
代码：
#pragma comment(linker, "/STACK:102400000,102400000")
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<string>
#include<cstdio>
#include<bitset>
#include<vector>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<set>
#include<map>
using namespace std;
#define debug test
#define mst(ss,b) memset((ss),(b),sizeof(ss))
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define inf 0x3f3f3f3f
#define eps 1e-10
#define PI acos(-1.0)
typedef pair<int,int> PII;
const ll mod = 1e9+7;
const int N = 1e5+2;ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qp(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int to[4][2]={{-1,0},{1,0},{0,-1},{0,1}};ll f[N],inv[N],ans[N],t,bk;
void init() {f[0]=f[1]=1;for(int i=2;i<N;i++) f[i]=f[i-1]*i%mod;inv[N-1]=qp(f[N-1],mod-2);for(int i=N-2;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}ll C(ll n,ll m) {if(n<m) return 0;else return f[n]*inv[m]%mod*inv[n-m]%mod;
}struct nd{ll l,r,id;
}q[N];bool cmp(nd a,nd b) {if(a.r/bk==b.r/bk) return a.l<b.l;return a.r/bk<b.r/bk;
}
/*
或者
bool cmp(nd a,nd b) {if(a.l/bk!=b.l/bk) return a.l<b.l;return a.r<b.r;
}
*/
void mo() {sort(q+1,q+t+1,cmp);ll s=2,cl=1,cr=1;for(int i=1;i<=t;i++) {while(cl<q[i].l) {cl++;s = (2*s-C(cl-1,cr)+mod)%mod;}while(cl>q[i].l) {s = (s+C(cl-1,cr))%mod*inv[2]%mod;cl--;}while(cr<q[i].r) {cr++;s = (s+C(cl,cr))%mod;}while(cr>q[i].r) {s = (s-C(cl,cr)+mod)%mod;cr--;}ans[q[i].id]=s;}for(int i=1;i<=t;i++) cout<<ans[i]<<endl;
}int main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>t;init();bk=sqrt(N);for(int i=1;i<=t;i++) {cin>>q[i].l>>q[i].r;q[i].id=i;}mo();return 0;
}
这篇关于hdu 6333 Harvest of Apples的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
