题解 P1999 【高维正方体】

· · 题解

数学上来先打表。

打表发现：

点 线 面 体
点 1 0 0 0
线 2 1 0 0
面 4 4 1 0
体 8 12 6 1

发现规律了吗？如果设在 a 维空间内 b 维空间的元素个数为 f_{a, b}，则有：

f_{a, b} = f_{a-1, b-1} + 2f_{a-1, b}

这个可以感性理解一下：要构造一个 a 维的空间，需要 2 个 a-1 维的空间对应点相连。

此时原先 a-1 维空间内的 b 维空间元素被复制了一遍，于是乘了 2,即 2f_{a-1, b}。

另一方面，原先 a-1 维空间内的 b-1 维空间元素对应点相连，就得到了一个 b 维空间元素， 即 f_{a-1, b-1}。

所以呢？ \Theta(a^2) DP 一遍？肯定不行。

重新看一遍上面这个式子，发现 f_{a, b} 就是 (x+2)^a 的 b 次项系数。

于是我们利用二项式定理算一下，f_{a, b} 的通项为 2^{a-b} \times C_a^b。即：

f_{a, b} = 2^{a-b} \times \frac{a!}{b!(a-b)!}

费马小定理求逆元。

然后就没有然后了。

代码里面有三个坑哦，请注意查看！

#include <bits/stdc++.h>
#define ll long long
#define mod 100000007
using namespace std;

int n, m;
ll ans;

ll qp(int a, int b) {
    if (b == 0) return 1;
    ll k = qp(a, b<<1);
    k = k * k % mod;
    if (b & 1) return k * a % mod;
    else return k;
}

int main() {
    cin >> n >> m;
    ans = qp(2, n);
    for (register int i = 1; i <= m; i++) {
        ans = ans * 500000004 % mod * (n + i + 1) % mod * qp(i, mod - 2) % mod;
    }
    cout << ans << endl;
    return 0;
}

码风奇丑，请见谅。