Time Limit: 6 Sec Memory Limit: 128 MB
Submit: 73 Solved: 14
Description
Input
多组输入数据。
每组数据：
第一行两个整数n，r（1 <= r <= n <= 1000000）。
第二行r个不同的整数表示：集合S的一个r子集。
Output
每组数据输出一个整数表示有多少r子集小于给定的r子集。结果mod 1000000007（1e9 + 7）。
Sample Input
Sample Output
HINT
Source
----------------------------------------------------------------------------------------------
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+), M(1e9+);
typedef long long LL;
int a[N];
LL f[N]; int Pow(int n, int m, int p){
LL res=, t=n;
for(; m; ){
if(m&) res*=t, res%=p, m--;
else t*=t, t%=p, m>>=;
}
return res;
} int inverse(int x, int p){
return Pow(x, p-, p);
} LL C(int n, int k, int p){
if(n< || k< || n<k) return ;
return f[n]*inverse(f[k]*f[n-k]%p, p)%p;
} int main(){
f[]=;
for(int i=; i<N; i++) f[i]=f[i-]*i%M; for(int n, r; cin>>n>>r; ){
for(int i=; i<=r; i++) cin>>a[i];
sort(a, a+r+);
LL ans=;
for(int i=; i<=r; i++)
for(int j=a[i-]+; j<a[i]; j++){
ans+=C(n-j, r-i, M), ans%=M;
}
cout<<ans<<endl;
}
return ;
}
对于求和\[\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$项，仍然超时。
总而言之，这是一道好题。