隐藏
「成都七中D4T2」逃离地域岛 - 递推+组合数 | Bill Yang's Blog
0%

「成都七中D4T2」逃离地域岛 - 递推+组合数

题面


题目大意

求$n$维空间中,$k$条超平面($n-1$维)最多能将空间分割为几部分?

题目分析

设$f[i,j]$表示$j$维空间中,$i$条超平面能将空间分为最多的部分数。
假设我们现在要加入第$i$条超平面,我们想要让其尽量与前面的超平面相交,转化为子问题($j-1$维中的最多部分)。

发现这就是组合数的式子!
但是$f[i,j]$并不是$C_i^j$,因为边界不同。

相当于将杨辉三角翻转了一下接上去,故答案等价于:

代码

个人习惯,$n$表示超平面条数,$k$表示空间维度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const LL mod=1e9+7;

LL Quick_Pow(LL a,LL b) {
LL sum=1;
for(; b; a=a*a%mod,b>>=1)if(b&1)sum=sum*a%mod;
return sum;
}

LL n,k,last=1,ans=1;

int main() {
n=Get_Int();
k=Get_Int();
for(int i=1; i<=k; i++) {
last=last*Quick_Pow(i,mod-2)%mod*(n-i+1)%mod;
ans=(ans+last)%mod;
}
printf("%lld\n",ans);
return 0;
}

姥爷们赏瓶冰阔落吧~