HDU-6333 Problem B. Harvest of Apples 莫队

HDU-6333

题意：

有n个不同的苹果，你最多可以拿m个，问有多少种取法，多组数据，组数和n，m都是1e5，所以打表也打不了。

思路：

这道题要用到组合数的性质，记S（n，m）为从n中最多取m个的方法总数，显然是C（n，0），C（n，1）……C（n，m)的和。

显然S（n,m+1) = S(n, m) + C(n,m+1);

还有一个等式就不那么明显了，S（n+1,m) = 2 * S(n,m) - C(n,m);

我也是在王神犇的指导下明白的。

既然知道了一组（n，m）是可以在很快的时间下转移到（n+1，m),(n-1,m),(n,m+1),(n,m-1)的，这个时候就要想到莫队。把每一组的n和m转化成区间的右端点和左端点，是不是很神奇。

那如何求组合数C（n，m）？可以先预处理出n的前缀阶乘，每次除一下，就可以得到，当然，因为是取模意义下，这里除一下就要去乘以这个数的逆元。

这题还有个细节就是要先更新作为n的右端点，为了防止右端点小于左端点的情况出现，即n 比 m 小。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <string>

#include <vector>

#include <map>

#include <set>

#include <queue>

#include <list>

#include <cstdlib>

#include <iterator>

#include <cmath>

#include <iomanip>

#include <bitset>

#include <cctype>

#include <iostream>

using namespace std;

//#pragma comment(linker, "/STACK:102400000,102400000")  //c++

#define lson (l , mid , rt << 1)

#define rson (mid + 1 , r , rt << 1 | 1)

#define debug(x) cerr << #x << " = " << x << "\n";

#define pb push_back

#define pq priority_queue

typedef long long ll;

typedef unsigned long long ull;

typedef pair<ll ,ll > pll;

typedef pair<int ,int > pii;

//priority_queue<int> q;//这是一个大根堆q

//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q

#define fi first

#define se second

// #define endl '\n'

#define OKC ios::sync_with_stdio(false);cin.tie(0)

#define FT(A,B,C) for(int A=B;A <= C;++A)  //用来压行

#define REP(i , j , k)  for(int i = j ; i <  k ; ++i)

//priority_queue<int ,vector<int>, greater<int> >que;

const ll mos = 0x7FFFFFFF;  //

const ll nmos = 0x80000000;  //-2147483648

const int inf = 0x3f3f3f3f;

const ll inff = 0x3f3f3f3f3f3f3f3f; //

template<typename T>

inline T read(T&x){

    x=;int f=;char ch=getchar();

    while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x=f?-x:x;

}

// #define _DEBUG;         //*//

#ifdef _DEBUG

freopen("input", "r", stdin);

// freopen("output.txt", "w", stdout);

#endif

/*-----------------------show time----------------------*/

                #define bel(x) ((x-1)/B+1)

                const int maxn = 1e5+;

                const int B = ;

                const int MOD = 1e9+;

                ll ans[maxn];

                struct node {

                    int n,m;

                    int id;

                } p[maxn];

                ll X,Y;

                void exgcd(ll a,ll b){

                    if(b==){

                        X = ;Y = ;

                        return;

                    }

                    exgcd(b,a%b);

                    ll tmp = X;

                    X = Y;

                    Y = tmp - a/b*Y;

                }

                bool cmp(const node &a,const node &b){

                    if(bel(a.m) == bel(b.m))

                        return a.n < b.n;

                    return bel(a.m) < bel(b.m);

                }

                ll pm[maxn],TWO,NY[maxn];       //NY是预处理的逆元，不出来会TLE

                void init(){

                    pm[] = ;

                    exgcd(,MOD);

                    NY[] = (X + MOD)%MOD;

                    for(int i=; i<maxn; i++){

                        pm[i] = (pm[i-] * i + MOD) % MOD;

                        exgcd(pm[i],MOD);

                        NY[i] = (X + MOD)%MOD;

                    }

                    exgcd(,MOD);

                    TWO = (X + MOD)%MOD;

                }

                ll get(int n, int x){

                        if(n-x < )return ;

                        ll res = (pm[n] *NY[n-x])%MOD;

                        res = (res * NY[x])%MOD;

                        return res;

                }

                ll sum = ;

                void del1(int x,int n){

                    sum =(sum- get(n,x)+MOD)%MOD;

                }

                void add1(int x,int n){

                    sum=(sum + get(n,x) +MOD)%MOD;

                }

                void del2(int x,int n){

                    sum = ((sum + get(n,x))*TWO + MOD)%MOD;

                }

                void add2(int x,int n){

                    sum = (sum *  - get(n,x)+MOD)%MOD;

                }

int main(){

                init();

                int q;

                scanf("%d", &q);

                for(int i=; i<=q; i++){

                    scanf("%d%d",&p[i].n,&p[i].m);

                    p[i].id = i;

                }

                sort(p+,p++q,cmp);

                int pl = p[].m, pr = p[].n;

                for(int i=; i<=pl; i++)

                {

                    sum = (sum + get(pr,i) + MOD)%MOD;

                }

                ans[p[].id] = sum;

               // cout<<"**"<<endl;

                for(int i=; i<=q; i++){

                    while(pr < p[i].n) add2(pl,pr),pr++;//这里要先更新作为n的右区间，防止m>n;

                    while(pr > p[i].n) pr--,del2(pl,pr);

                    while(pl < p[i].m) pl++,add1(pl,pr);

                    while(pl > p[i].m) del1(pl,pr),pl--;

                    ans[p[i].id] = sum%MOD;

                }

                for(int i=; i<=q; i++){

                    printf("%lld\n", ans[i]);

                }

        return ;

}

HDU6333

巴特西

HDU-6333 Problem B. Harvest of Apples 莫队

题意：

思路：

最新文章

热门文章