题解 P1999 【高维正方体】

· · 题解

神仙题

分析法是个好方法

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

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