900字范文 > 关于m个n-1维几何体最大分割n维空间问题的解法

关于m个n-1维几何体最大分割n维空间问题的解法

时间：2019-09-05 10:58:19

1.前置知识2.空间关系与基本递推式3.递推式的优化4.程序的进一步优化5.AC代码6.总结7.测试数据

定义 f(n,m)f(n,m)f(n,m) 表示n个m-1维几何体最大分割m维空间的个数，求给定的n,m的 f(n,m)f(n,m)f(n,m)对1e9+7取模。(n<=1e9,m<=1e7)

时间限制：1s 空间限制： 512mb

例如，f(1,2)=2;f(2,3)=4;f(3,3)=8f(1,2)=2;f(2,3)=4;f(3,3)=8f(1,2)=2;f(2,3)=4;f(3,3)=8。（画下图就能理解了）

然后试着去想一下为什么f(4,3)=15f(4,3)=15f(4,3)=15（不是14，要细致考虑怎么画图）。

接下来开始细致讲解。

1.前置知识

一定的空间想象能力，逆元，组合数，杨辉三角。

2.空间关系与基本递推式

如果你能推出来f(4,3)=15f(4,3)=15f(4,3)=15并能归纳出递推式的话，你的理解力已经很强了，可以直接看第三部分了。

好，f(3,3)f(3,3)f(3,3)是在三个维度上各切一刀，这个是很显然的，那么f(4,3)f(4,3)f(4,3)一定是在这三刀的基础上切的，怎么切呢？

我们先来考虑直线分割平面，在两个维度个切一刀后，我们考虑f(3,2)f(3,2)f(3,2)的情况。

显然，为了分割最大，我们让第三条直线与已经切好的两条直线都相交。这样子我们顺利得到了f(3,2)=7f(3,2)=7f(3,2)=7。

实际上，我们继续考虑：

f(3,2)=7;f(2,1)=3;f(2,2)=4;f(3,2)=7;f(2,1)=3;f(2,2)=4;f(3,2)=7;f(2,1)=3;f(2,2)=4;

你是否发现了什么？

继续考虑f(4,2)

将三条直线都经过一次，我们显然得到了f(4,2)=11f(4,2)=11f(4,2)=11。

继续往下考虑:

f(4,2)=11;f(3,1)=4;f(3,2)=7;f(4,2)=11;f(3,1)=4;f(3,2)=7;f(4,2)=11;f(3,1)=4;f(3,2)=7;

那么回到f(4,3)f(4,3)f(4,3)上。

我们类比二维的，让第四个平面与已经切好的三个平面相交。

f(4,3)=15;f(3,2)=7;f(3,3)=8;f(4,3)=15;f(3,2)=7;f(3,3)=8;f(4,3)=15;f(3,2)=7;f(3,3)=8;

因为高维空间无法直观观察，所以我们递推：

现在是m维的已经切好了n-1刀，有：

1 .如果还有维度没有分割，分割这个维度。

2 .维度都分割完了，那么把所有已分割的“刀”都经过一次。

归纳一下，实际上就是新的一“刀”要把之前的“刀”全经过一次。

至此，我们已经得到基本递推式：

f(n,m)=f(n−1,m−1)+f(n−1,m)f(n,m)=f(n-1,m-1)+f(n-1,m)f(n,m)=f(n−1,m−1)+f(n−1,m)

3.递推式的优化

上述方法的复杂度是O(nm)O(nm)O(nm)的，只能通过60pts。

我们思考怎么优化。

从特例入手，我们考虑展开f(4,4)f(4,4)f(4,4)。

f(4,4)=f(3,3)+f(3,4)f(4,4)=f(3,3)+f(3,4)f(4,4)=f(3,3)+f(3,4)

f ( 3 , 2 )=f(2,2)+2f(2,3)+f(2,4)=f(2,2)+2f(2,3)+f(2,4)=f(2,2)+2f(2,3)+f(2,4)

f ( 3 , 2 )=f(1,1)+3f(1,2)+3f(1,3)+f(1,4)=f(1,1)+3f(1,2)+3f(1,3)+f(1,4)=f(1,1)+3f(1,2)+3f(1,3)+f(1,4)

f ( 3 , 2 )=f(0,0)+4f(0,1)+6f(0,2)+4f(0,3)+f(1,4)=f(0,0)+4f(0,1)+6f(0,2)+4f(0,3)+f(1,4)=f(0,0)+4f(0,1)+6f(0,2)+4f(0,3)+f(1,4)

很显然，只要是维度大于0的空间，什么都不做只有自己这一份，所以f(0,m>=0)=1f(0,m>=0)=1f(0,m>=0)=1

然后我们观察展开过程中，系数都是杨辉三角上的数。

根据组合数学知识，我们很容易知道，杨辉三角上的数对应是这一层的组合数。

第x层上都是Cx0−>x+1C^{0->x+1}_xCx0−>x+1(定义顶层为第0层)。

那么很显然，当n>=m时，杨辉三角不会出现溢出的情况（溢出是与n < m相对的），答案就是分解到n=0时候这一层杨辉三角的和，对应化简式：

∑i=0nCni\sum_{i=0}^nC^i_n∑i=0nCni

由组合知识可以得到和为2n2^n2n

那么当n < m的时候，我们很容易发现这个时候杨辉三角溢出了（即存在n降到0时展开式有m为负数的情况，可以自己展开一个式子理解一下溢出）。

很显然，从几何意义来看，那些溢出的部分是0，怎么可能存在负维的几何空间（至少这道题不涉及，可能未来会存在？）。

那么会发现，我们从n-m到-1这些部分都是0（这里指组合数C的第二个参数），只需要考虑n这层杨辉三角从0到m的项。

那么显然，答案就是：

∑i=0mCni\sum_{i=0}^mC^i_n∑i=0mCni

归纳之后，发现第一种情况实际上可以并入第二种情况之中。

所以，最终结果就出来了。

f(n,m)=∑i=0mCnif(n,m)=\sum_{i=0}^mC^i_nf(n,m)=∑i=0mCni

到现在，这道题可以拿90pts了。(毕竟还有n<=1e9的毒瘤数据)

4.程序的进一步优化

上述的式子用阶乘逆元求组合数时间复杂度看似是O(max(n,m))O(max(n,m))O(max(n,m))，实际上常数非常大，加之n可能是1e9所以这种算法显然是AC不掉的。

所以必须先预处理逆元，然后递推组合数，这部分知识忘记要复习啊，这是很简单的，实在不会可以看代码。

然后还有一个细节处理，我们知道组合数也可以递推，所以我们多推一层，这样，我们的总时间复杂度是O(m+m/2)O(m+m/2)O(m+m/2)。(不要忘了m也很大，常数大点不优化是过不去的。)

至此，本题AC。

5.AC代码

AC链接

#include<bits/stdc++.h>//author:Displaceusing namespace std;typedef long long ll;const ll mod=1e9+7;int n,m;ll inv[10100000];ll c[10100000];int main(){scanf("%d%d",&n,&m);inv[0]=inv[1]=1;for(int i=2;i<=m;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;//递推逆元c[0]=1;ll ans=0;for(int i=0;i<=m;i++)c[i+1]=c[i]*(n+1-i)%mod*inv[i+1]%mod;//递推组合数for(int i=m;i>=0;i-=2) ans=(ans+c[i])%mod;//求和printf("%lld\n",ans);return 0;}