bzoj 4403 序列统计卢卡斯定理

2021-11-04 20:36:16

4403：序列统计

Time Limit: 3 Sec Memory Limit: 128 MB

Description

给定三个正整数N、L和R，统计长度在1到N之间，元素大小都在L到R之间的单调不降序列的数量。输出答案对10^6+3取模的结果。

Input

输入第一行包含一个整数T，表示数据组数。第2到第T+1行每行包含三个整数N、L和R，N、L和R的意义如题所述。

Output

输出包含T行，每行有一个数字，表示你所求出的答案对106+3取模的结果。

Sample Input

1 4 5

2 4 5

Sample Output

HINT

提示

【样例说明】满足条件的2个序列为[4]和[5]。

【数据规模和约定】对于100%的数据，1≤N,L,R≤10^9，1≤T≤100，输入数据保证L≤R。

思路：得到一个这样的二维数组：表示第i的长度结尾为L的个数

　　　L L+1 L+2 L+3 ....... R

1 1 1 1 1 ...... 1

2 1 2 3 4 ...... R

.....

N 1 C(N,1) ...... C((R-L+1+N),N)

答案为取一个矩阵的和，sigma；

#include<iostream>

#include<cstdio>

#include<cmath>

#include<string>

#include<queue>

#include<algorithm>

#include<stack>

#include<cstring>

#include<vector>

#include<list>

#include<set>

#include<map>

using namespace std;

#define ll long long

#define mod 1000000007

#define inf 999999999

#define pi 4*atan(1)

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

int scan()

{

    int res =  , ch ;

    while( !( ( ch = getchar() ) >= '' && ch <= '' ) )

    {

        if( ch == EOF ) return  <<  ;

    }

    res = ch - '' ;

    while( ( ch = getchar() ) >= '' && ch <= '' )

        res = res *  + ( ch - '' ) ;

    return res ;

}

ll f[];

void init(int p) {                 //f[n] = n!

    f[] = ;

    for (int i=; i<=p; ++i) f[i] = f[i-] * i % p;

}

ll pow_mod(ll a, ll x, int p)   {

    ll ret = ;

    while (x)   {

        if (x & )  ret = ret * a % p;

        a = a * a % p;

        x >>= ;

    }

    return ret;

}

ll Lucas(ll n, ll k, ll p) {       //C (n, k) % p

     ll ret = ;

     while (n && k) {

        ll nn = n % p, kk = k % p;

        if (nn < kk) return ;                   //inv (f[kk]) = f[kk] ^ (p - 2) % p

        ret = ret * f[nn] * pow_mod (f[kk] * f[nn-kk] % p, p - , p) % p;

        n /= p, k /= p;

     }

     return ret;

}

int main()

{

    ll x,y,z,i,t;

    init();

    int T;

    ll N,L,R;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%lld%lld%lld",&N,&L,&R);

        ll n,k;

        ll ans=;

        k=N;

        n=(R-L++N);

        ans+=Lucas(n,k,);

        printf("%lld\n",(ans+)%);

    }

    return ;

}

码农公寓