洛谷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;
}