HDU 5145 - NPY and girls

题意： cases T(1≤T≤10) (0<n,m≤30000) (0<ai≤30000)
　　

　　　　n个数ai 表示n个女孩所在教室

　　　　m次询问 [L,R]（1 <= L <= R <= n）
　

　　　　问访问所有女孩的顺序方案数(进教室顺序)为多少(一次进教室只能访问一个人)

分析：

　　　　莫队算法 + 排列数

　　　　一个区间内的方案数为 C(m,c1)*C(m-c1,c2)*C(m-c1-c2,c3)*....*C(cn,cn)
　　

　　　　每次转移通过下式：

　　　　 C(m+1,n+1) = C(m,n) * (m+1/n+1)
　　

　　　　 C(m,n) = C(m+1,n+1) * (n+1/m+1) （对于缩小的过程而言）

　　因为需要对大素数取模，除法就是乘上对应的乘法逆元，故先用费马小定理

#include <iostream>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <cstring>

using namespace std;

const int MOD = ;

const int MAXN = ;

const int MAXM = ;

struct Query

{

    int L,R,id;

}node[MAXM];

struct Ans

{

    long long a;

}ans[MAXM];

int a[MAXN],num[MAXN];

long long inv[MAXN];//乘法逆元

int t,n,m,unit;

void work()

{

    long long temp = ;

    memset(num,,sizeof(num));

    int L =  , R = ;

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

    {

        while(R < node[i].R)//C(m+1,n+1) = C(m,n)*(m+1/n+1)

        {

            R++;

            num[a[R]]++;

            temp = temp * (R - L + ) % MOD * inv[num[a[R]]] % MOD;

        }

        while(R > node[i].R)//C(m,n) = C(m+1,n+1)*(n+1/m+1)

        {

            temp = temp * num[a[R]] % MOD * inv[R - L + ] % MOD;

            num[a[R]]--;

            R--;

        }

        while(L < node[i].L)//C(m,n) = C(m+1,n+1)*(n+1/m+1)

        {

            temp = temp * num[a[L]] % MOD * inv[R - L + ] % MOD;

            num[a[L]]--;

            L++;

        }

        while(L > node[i].L)//C(m+1,n+1) = C(m,n)*(m+1/n+1)

        {

            L--;

            num[a[L]]++;

            temp = temp * (R - L + ) % MOD * inv[num[a[L]]] % MOD;

        }

        ans[node[i].id].a = temp;

    }

}

bool cmp(Query a,Query b)

{

    if(a.L/unit != b.L/unit) return a.L/unit < b.L/unit;

    else return a.R < b.R;

}

void Init()//femat

{

    inv[] = ;

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

        inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;

}

int main()

{

    Init();

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d",&n,&m);

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

            scanf("%d",&a[i]);

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

        {

            scanf("%d%d",&node[i].L,&node[i].R);

            node[i].id = i;

        }

        unit = (int)sqrt(n);

        sort(node,node+m,cmp);

        work();

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

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

    }

}

巴特西

HDU 5145 - NPY and girls

最新文章

热门文章