BZOJ 4403: 序列統計（組合數 Lucas 數論推導）

BZOJ 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的意義如題所述。

1≤N,L,R≤10^9，1≤T≤100，輸入資料保證L≤R。

Output

輸出包含T行，每行有一個數字，表示你所求出的答案對10^6+3取模的結果。

Sample Input

1 4 5

2 4 5

Sample Output

思路：

一道标準的排列組合題目，不過思維很是巧妙，辣雞的我困擾了許久。

這道題目我們很容易想到一位一位的去考慮，相鄰位數之間的遞推關系不難發現，但讓人崩潰的是1e9的資料規模，遞推肯定挂得死死的。雖然無奈但是我們還是确定了思路，一個式子解決問題！

然後。。。額，活生生被搞成了一道數學題。

進過多次嘗試後，我絕望地發現，好像并沒有什麼公式或方法可以直接解決這一問題，那麼還是隻能對于1~n中的一個i進行分析。我們發現無論我們選出來哪一些數，針對于這些數，有且隻有一種排列方式讓它滿足單調不降（相同數之間交換認為是同一種）。

是以就成了組合問題。如果是單純的C（m，i），并不包含一種元素可以多選的情況，那如果我們每個元素都取i個呢？->C(m*i,i)顯然也是有問題的。eg：2 4 5這一組資料，本來是（4 5）隻有4,5 4,4 5,5，現在變成了（4 4 5 5）有4,4 4,5 4,5 4,5 4,5 5,5。為什麼呢？因為我們的組合數把兩個4，當做了不同的兩個數，就多了很多重複的情況。是以說如果我們要添加元素的話，隻能增加有數字重複的狀态，而不能增加原有的狀态。那麼我們考慮不去添加數，而是去添加一些符号，來表示這些重複的數字。eg：還是2 4 5這一組資料，我們添加一個+号，來表示它是某個數後邊第一個和它相同的數， 4，+ 就代表4,4 ； 5，+就代表5,5；那麼我們就有了三個元素（4 5 +）；方案就有4,5；4，+；5，+三種，這種方法既解決了有數字重複的情況，又不影響沒有數字的情況。

找到了解決方法，做普遍推廣，對于i位數，我們添加i-1個符号（最多有i個重複數字），是以方案數就是C(m+i-1,i)。

現在隻剩下sigma的問題了，（當然不能for一遍sum）。因為C(m,n)=C(m-1,n)+C(m-1,n-1)，在m個東西中取n個，可以分成兩類，【（1）不取第一個，那麼就是在剩下的m-1個裡面取n個。（2）取了第一個，那麼就是在剩下的m-1個裡面取n-1個。】

我們要求的答案就是，C(m+n-1,n)+C(m+n-2,n-1)+…+C(m+1,2)+C(m,1）；

如果我們在式子的末尾添上一個C(m,0)；

原式就變成了C(m+n-1,n)+C(m+n-2,n-1)+…+C(m+1,2)+C(m,1）+C(m,0)；

因為C(m,1）+C(m,0)=C(m+1,1)；

是以原式=C(m+n-1,n)+C(m+n-2,n-1)+…+C(m+1,2)+C(m+1,1)；

又因為C(m+1,1）+C(m+1,2)=C(m+2,2)；

是以原式=C(m+n-1,n)+C(m+n-2,n-1)+…+C(m+2,2)；

…最終ans就是C(m+n，n)；

因為我們加上了一個C(m,0)；是以最後減掉一個1。

我們求C(m+n，n) - 1！完美！！

然後就是Lucas，逆元求組合數了。

注意一下，因為我們最後要-1，ans可能為負，是以我們做一個處理 ( ans ) % mod + mod ) % mod 。

如果下面的操作還有不懂的話請轉至組合數

#include <cstdio>
#include <iostream>
#define LL long long
using namespace std;

const LL mod =  + ;

LL mub[mod+];
LL x, y;

void init(){//初始化階乘..超過mod
    mub[] = ;//注意細節
    for(int i=; i<=mod+; i++){
        mub[i] = mub[i-] * i % mod;
    }
}

LL exgcd(LL a, LL b, LL &x, LL &y){//擴充歐幾裡得求逆元
    if(a ==  && b == )
        return -;
    if(b == ){
        x = ; y = ;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
        y -= a / b * x;
    return d;
}

LL mod_reverse(LL a, LL n){
    LL d = exgcd(a, n, x, y);
    if(d == )
        return ( x % n + n ) % n;
    else
        return -;
}

LL solve(LL a, LL b){
    if(a > b) return ;//
    LL nn = mod_reverse((mub[a] * mub[(b + mod - a) % mod]) % mod, mod);
    return mub[b] * nn % mod;
}

void to_solve(LL a, LL b){//Lucas
    if(b < mod){
        solve(a, b);
        return;
    }
    printf("%lld\n", ( (solve(a/mod, b/mod) * solve(a%mod, b%mod) -  ) % mod + mod ) % mod );//
}

int main(){
    int T; scanf("%d", &T);
    init();
    while ( T-- ){
        LL n, l ,r;
        scanf("%lld%lld%lld", &n, &l, &r);
        LL m = r - l + ;
        if(m + n < mod){
            printf("%lld\n", ( ( solve(n, m+n) -  ) % mod + mod ) % mod );//
        }
        else to_solve(n, m+n);
    }
    return ;
}

BZOJ 4403: 序列統計（組合數 Lucas 數論推導）