hdu 6333-数論+莫隊

タイトルリンク:ここをクリック
 
問題解決の考え方:
またS(n,m)＝c(n,0)＋c(n,1)＋c(n,2)＋…＋c(n,m)
ではS(n,m)=S(n,m−1)+c(n,m)
またc(n+1,1)+c(n+1,2)+...+c(n+1,m) = S(n,m)+c(n,1)+c(n,2)+c(n,3) +...c(n,m−1)->c(n+1,k)=c(n,k)+c(n,k−1)から得られる
両側+1得:c(n+1,0)+c(n+1,1)+c(n+1,2)+...+c(n+1,m) = S(n,m)+c(n,0)+c(n,1)+c(n,2)+c(n,3) +...c(n,m-1)
S(n+1,m) = 2*S(n,m) - c(n,m)
S(n,m)を知れば,S(n+1,m),S(n−1,m),S(n,m+1),S(n,m+1),S(n,m−1)をO(1)で知ることができる.
mをlと見なし,nをrと見なし,ブロックを分けて莫隊を走る.時間の複雑さはO(n*ルートn)です.
 

#include
using namespace std;
const int mx = 1e5 + 10;
const int mod = 1e9 + 7;
typedef long long ll;
ll inv[mx],f[mx],ans[mx];
int n,m,block;
struct node
{
    int l,r;
    int pos;
    bool operator < (node A)const
    {
        if(l/block!=A.l/block) return l < A.l;
        return r < A.r;
    }
}s[mx];
void init(){
    inv[0] = inv[1] = 1;
    for(int i = 2; i < mx; i++){
        inv[i] = (ll)(mod-mod/i)*inv[mod%i]%mod;
    }
    f[0] = 1;
    for(int i = 1; i < mx; i++){
        f[i] = f[i-1]*i%mod;
    }
    for(int i = 1; i < mx; i++){
        inv[i] = inv[i]*inv[i-1]%mod;
    }
    for(int i=mx-2;i>=1;i--) inv[i] = inv[i+1]*(i+1)%mod; 
}
int main()
{
    int t,ma = 0;
    scanf("%d",&t);
    init();
    for(int i=1;i<=t;i++){
        scanf("%d%d",&s[i].r,&s[i].l);
        ma = max(ma,s[i].r);
        s[i].pos = i;
    }
    block = sqrt(ma);
    sort(s+1,s+1+t);
    int L = 0,R = 0;
    ll val = 1;
    for(int i=1;i<=t;i++){
        while(Rs[i].r) R--,val = (val+f[R]*inv[L]%mod*inv[R-L]%mod)%mod*inv[2]%mod;
        while(Ls[i].l) val = (val-f[R]*inv[L]%mod*inv[R-L]%mod+mod)%mod,L--;
        ans[s[i].pos] = val;
    }
    for(int i=1;i<=t;i++) printf("%lld
",ans[i]);
    return 0;
}