自动搬运

查看原文

来自洛谷，原作者为

	ghj1222 阿绫最可爱啦

搬运于2025-08-24 21:32:47，当前版本为作者最后更新于2018-09-05 17:29:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

神仙题

分析法是个好方法

反正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定理

让我们一起膜拜大佬林瑞堂