DLUTOJ 1209 字典序和r-子集

傷城~ 2021-12-05 15:07 228阅读 0赞

[ 传送门][Link 1]

**Time Limit:** 6 Sec **Memory Limit:** 128 MB  
**Submit:** 73 **Solved:** 14

## Description ##

![a1.png][]

## Input ##

多组输入数据。

每组数据：

第一行两个整数n，r（1 <= r <= n <= 1000000）。

第二行r个不同的整数表示：集合S的一个r子集。

## Output ##

每组数据输出一个整数表示有多少r子集小于给定的r子集。结果mod 1000000007（1e9 + 7）。

## Sample Input ##

3 2 2 3 3 1 2

## Sample Output ##

2 1

## HINT ##

## Source ##

[sspa][]

\----------------------------------------------------------------------------------------------

**Solution:**

对于\$S=\\\{1, 2, ..., n\\\}\$的两个r子集\$A, B，B<A\$的条件是只属于$A$或只属于$B$的元素中最小的那个元素$x$属于$B$。

因此我们可以枚举$x$，$B$中小于$x$的元素也在$A$中，大于$x$的元素可以在$(x, n\]$上任意选取。

设$A$的元素为：

\\\[1\\le a\_\{1\}<a\_\{2\}<a\_\{3\}<\\dots<a\_\{r\}\\le n\\\]

另外设\\\[a\_\{0\}=0\\\]

则答案为

\\\[\\sum \_\{i=1\}^\{r\}\\sum\_\{j=a\_\{i-1\}+1\}^\{a\_\{i\}-1\}\\binom\{n-j\}\{r-i\}\\\]

容易看出这样总共要计算组合数\$0\\le a\_\{r\}-r\\le n-r\$次

**Implementation:**

#include <bits/stdc++.h>
    using namespace std;
    
    const int N(1e6+5), M(1e9+7);
    typedef long long LL;
    int a[N];
    LL f[N];
    
    int Pow(int n, int m, int p){
        LL res=1, t=n;
        for(; m; ){
            if(m&1) res*=t, res%=p, m--;
            else t*=t, t%=p, m>>=1;
        }
        return res;
    }
    
    int inverse(int x, int p){
        return Pow(x, p-2, p);
    }
    
    LL C(int n, int k, int p){
        if(n<0 || k<0 || n<k) return 0;
        return f[n]*inverse(f[k]*f[n-k]%p, p)%p;
    }
    
    
    int main(){
        f[0]=1;
        for(int i=1; i<N; i++) f[i]=f[i-1]*i%M;
        
        for(int n, r; cin>>n>>r; ){
            for(int i=1; i<=r; i++) cin>>a[i];
            sort(a, a+r+1);
            LL ans=0;
            for(int i=1; i<=r; i++)
                for(int j=a[i-1]+1; j<a[i]; j++){
                    ans+=C(n-j, r-i, M), ans%=M;
                }
            cout<<ans<<endl;
        }
        return 0;
    }

对于求和\\\[\\sum \_\{i=1\}^\{r\}\\sum\_\{j=a\_\{i-1\}+1\}^\{a\_\{i\}-1\}\\binom\{n-j\}\{r-i\}\\\]的计算我想过依据组合恒等式

\\\[\\binom\{0\}\{k\}+\\binom\{1\}\{k\}+\\binom\{2\}\{k\}+\\dots+\\binom\{n\}\{k\}=\\binom\{n+1\}\{k+1\}\\\]

将里面一项\\\[\\sum\_\{j=a\_\{i-1\}+1\}^\{a\_\{i\}-1\}\\binom\{n-j\}\{r-i\}\\\]合并成

\\\[\\binom\{n-a\_\{i-1\}\} \{r-i+1\} - \\binom\{n-a\_\{i\}+1\}\{r-i+1\}\\\]

但超时了，按这种算法，无论集合$A$的元素是什么，都要算$2r$次组合数，而在$r$比较大时，$2r$比$a\_\{r\}-r$大不少，超时是必然的。对于大数据，这种看似优化了的方法反而慢很多，所以凡事不能想当然！

我还试过把式子进一步化简成$r$项，仍然超时。

总而言之，这是一道好题。

转载于:https://www.cnblogs.com/Patt/p/5345771.html

[Link 1]: http://www.cnblogs.com/acm.dlut.edu.cn/problem.php?id=1209
[a1.png]: http://acm.dlut.edu.cn/upload/201403/a1.png
[sspa]: http://acm.dlut.edu.cn/problemset.php?search=sspa