bzoj4403 序列统计—

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4403

一开始想了个 O(n) 的做法，不行啊...

O(n)想法是这样的：先考虑递推，设 f[i][j] 为在第 i 个位置选第 j 个数字；

设 m = r-l+1；

那么 f[i][j] = ∑(1<=k<=j) f[i-1][k]，初值是 f[1][i] = 1 (1<=i<=m)；

那么 ans = ∑(1<=i<=n , 1<=j<=m) f[i][j]；

这个式子换个角度想，可以考虑初值的1贡献了几次；

对于每个 f[1][j]，发现它到 i=2 的位置贡献了 m - j 次，之后每次递推贡献了 ∑(1<=i<=m-j) i 次，也就是 C(m-j , 2) 次；

所以 ans = ∑(1<=i<=m) (C(i,2) * (n-2) + i) + m，其中最后加的 m 是 ∑(1<=i<=m) f[1][i]；

但这个时间复杂度是 O(n) 的，不行啊...

然后看了博客：https://blog.csdn.net/Clove_unique/article/details/68491395

竟然是如此简洁！我就是太关注那个序列，其实只需要选出几个数，之后再排序就好了啊！！

需要预处理阶乘逆元，而且别忘了处理 0 的逆元。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long ll;

int const mod=1e6+;

int T,n,l,r,m;

ll ans,fac[mod+],inv[mod+];

ll pw(ll a,ll b)

{

    ll ret=;

    for(;b;b>>=,a=(a*a)%mod)

        if(b&)ret=(ret*a)%mod;

    return ret;

}

void init()

{

    fac[]=;

    for(int i=;i<mod;i++) fac[i]=(fac[i-]*i)%mod;

    inv[mod-]=pw(fac[mod-],mod-);//不能求 inv[mod]

    for(int i=mod-;i>=;i--) inv[i]=(inv[i+]*(i+))%mod;//要处理出0的逆元！

}

ll C(int n,int m)

{

    if(n<m)return ;

//    ll a=1,b=1; m=min(m,n-m);

//    for(int i=n-m+1;i<=n;i++)a=(a*i)%mod;

//    for(int i=1;i<=m;i++)b=(b*i)%mod;

//    return (a*pw(b,mod-2))%mod;

    return ((fac[n]*inv[m])%mod*inv[n-m])%mod;

}

ll Lucas(ll n,ll m)

{

    if(m==)return ;

    return (C(n%mod,m%mod)*Lucas(n/mod,m/mod))%mod;

}

int main()

{

    init();

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d%d",&n,&l,&r); m=r-l+;

        ll ans=Lucas((ll)n+m,m)-;

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

    }

    return ;

}

巴特西

bzoj4403 序列统计——组合数学

最新文章

热门文章