洛谷P1999 高维正方体 题解

题目链接：P1999 高维正方体

题意：

$0$ 维空间的元素是点，这个毋庸置疑。

$2$ 个 $0$ 维空间的元素可以围成一个 $1$ 维空间的元素，线段。

$4$ 个 $1$ 维空间的元素可以围成一个 $2$ 维空间的元素，正方形。

$6$ 个 $2$ 维空间的元素可以围成一个 $3$ 维空间的元素，正方体。

$8$ 个 $3$ 维空间的元素可以围成一个 $4$ 维空间的元素，超正方体。

……

一个正方形中，有 $4$ 个（顶）点，$4$ 条线段（边），$1$ 个正方形。

一个正方体中，有 $8$ 个（顶）点，$12$ 条线段（棱），$6$ 个正方形（面），$1$ 个正方体。

……

我们的问题是：给出 $a$ 与 $b$ ，请求出：在 $a$ 维空间的元素中，包含着多少个 $b$ 维空间的元素。答案可能很大，只需要输出它除以 $10^9 + 7$ 的余数。

输入格式：

两个整数 $a,b$ ，以空格隔开。

输出格式：

一个整数，即答案。

数据范围：

$0 \le a,b \le 10^5$

画过 $4$ 维超立方体的平面图的，应该都秒了dp方程吧

我们先画一个正方体，再画一个它的平移，然后把顶点相连。如图：

设 $f_{i,j}$ 表示第 $i$ 维空间中第 $j$ 维物品的个数，则有

$$f_{0,0} = 1 \\[6pt] f_{i,j} = 2f_{i-1,j} + f_{i-1,j-1}$$

但这是一个 $\mathcal{O}(n^2)$ 的dp，因此考虑dp方程的通项

设 $F_i(x)$ 表示第 $i$ 维的生成函数，则

$$F_i(x) = \sum_{n\ge 0}f_{i,n}x^n$$

规定负下标的 $f$ 为 $0$ ，并将 $F_i(x)$ 代入转移方程里

$$\begin{aligned} F_i(x) &= (2 + x) F_{i-1}(x) \\[6pt]&=(2+x)^i \end{aligned}$$

则

$$\begin{aligned} f_{i,j} &= [x^j]F_i(x) \\[6pt] &=[x^j] (2+x)^i \\[6pt] &= [x^j]\sum_{r=0}^{i} \dbinom{r}{i}2^rx^{i-r} \\[6pt] &= \dbinom{i}{j}\times 2^{i-j} \\[6pt] &= 2^{i-j} \times \frac{i!}{j!\,(i-j)!} \end{aligned}$$

然后求个阶乘，求个逆元就好啦

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5+15))

const int mod = 1e9 + 7;
int qpow(int a,int b)
{
    int ans = 1, base = a % mod;
    for(; b; b >>= 1)
    {
        if(b & 1) ans = ans * base % mod;
        base = base * base % mod;
    }
    return ans;
}
int mul(int cnt, ...)
{
    va_list ptr; va_start(ptr,cnt); int res = 1;
    for(int i=0; i<cnt; i++) res = res * va_arg(ptr,int) % mod;
    va_end(ptr); return res;
}
int inv(int x) { return qpow(x, mod-2); }
int n,m,fac[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m; fac[0] = 1;
    if(m > n) return cout << "0\n", 0;
    for(int i=1; i<=n; i++) fac[i] = fac[i-1] * i % mod;
    cout << mul(4, qpow(2, n-m), fac[n], inv(fac[m]), inv(fac[n-m]));
    return 0;
}