神仙题
分析法是个好方法
反正xjb分析就分析出来了
首先，i维立方体的点数(0维元素数)为\(2^i\)
首先0维肯定是1(不就是一个点吗)
你想想你是怎么用点拼成线段的
你把两个点往地上一扔
然后中间连一条线
就完事儿了
然后你再想想你是怎么用线段拼成正方形的
你把两个长度相等的线段 往地上一方 摆成平行且间距等于他们长度 然后不就成了一个正方形了吗
然后你再想想你是怎么用正方形拼成正方体的
把两个全等的正方形 一个放下面 一个放上面 让这两个面平行 且间距等于正方形边长
由此
由i维立方体 拼成i+1维立方体
点数乘以2(因为每次你都是拿两个i维立方体拼成i+1维立方体)
所以i维立方体的点数(0维元素数)为\(2^i\)
然后递推求出i维立方体j维元素数，为了方便我们设为\(f[i][j]\)
则\(f[i][0]=2^i\)(刚才推得)
然后其余的怎么推
不好想
我们考虑i=3的情况
i=3,j=0的时候，\(f[3][0]=8(2^3=8)\)
然后考虑三维的立方体
每个顶点可以延伸出 三条边
而每条边连结2个顶点
根据某原理，\(\displaystyle f[3][1]=\frac{f[3][0]*3}{2}=12\)
然后呢每个边可以延伸出2个面
每个面连接着4个边
所以\(\displaystyle f[3][2]=\frac{f[3][1]*2}{4}=6\)
然后呢每个面 连接着1个正方体
没个正方体 连接6个面
所以 \(\displaystyle f[3][3]=\frac{f[3][2]*1}{6}=1\)
然后就找到规律了
\(\displaystyle f[3][j]=\frac{f[3][j-1]*(4-j)}{2*j}\)
然后呢推广到多维的情况
\(\displaystyle f[i][j]=\frac{f[i][j-1]*(i+1-j)}{2*j}\)
大功告成
复杂度\(O(nm)\)?放气儿
由于我们只求一个数，而且递推方程是在一行上递推的
所以我们先求出\(f[n][0]\)然后\(\displaystyle f[n][i]=\frac{f[n][i-1]*(n+1-i)}{2*i}\)
复杂度\(O(m)\)
由于需要取模
所以除法改为乘法逆元
由于1e9+7是素数
所以用快速幂/fermat小定理
一开始的\(f[n][0]=2^n\)也用快速幂
就行了
时间复杂度乘以一个log
代码
#include <bits/stdc++.h>
using namespace std;
#define p 1000000007
int f[100010], n, m;
int qpow(int x, int y)
{
int ans = 1;
while (y > 0)
{
if (y & 1)
ans = (1LL * ans * x) % p;
x = (1LL * x * x) % p;
y >>= 1;
}
return ans;
}
int main()
{
scanf("%d%d", &n, &m);
f[0] = qpow(2, n);
for (int i = 1; i <= m; i++)
f[i] = (1LL * f[i - 1] * (n - i + 1)) % p * qpow(2 * i, p - 2) % p;
printf("%d\n", f[m]);
return 0;
}
虽然慢了点
但是好分析
吊打各种lucas定理