【题解】P1999 高维正方体

P1999 高维正方体

去科普一下四维超立方体还是很好玩的~

制表如图

if[i][j]j	0	1	2	3	4	5	6	7	8
1	2	1	0
2	4	4	1	0
3	8	12	6	1	0
4	16	30	24	8	1	0
5	32	80	80	40	10	1	0
6	64
7

观察得 (f[i][0] = 2 ^ i)。

分析 i = 3 的情况：

一共8个点，每个点延伸出3条边，每条边被2个点共用，所以 (f[3][1] = frac{f[3][0] * 3} {2} = 12)；

一共12条边，每条边延伸出2个面，每个面由4条边构成，所以 (f[3][2] = frac{f[3][1] * 2} {4} = 6)；

一共6个面，每个面连出一个正方体，每个正方体由6个面构成，所以 (f[3][3] = frac{f[3][2] * 1}{6} = 1)

推广出来通式：(f[i][j] = frac{f[i][j - 1] * (i + 1 - j)}{j * 2})。

分析 i = 4，即4维超立方体的情况：

一共16个点，每个点延伸出4条边，每条边被2个点共用；

一共30条边，每条边延伸出3个面，每个面由4条边构成；

一共24个面，每个面延伸出2个正方体，每个正方体由6个面构成；

一共8个正方体，每个正方体延伸出1个四维超立方体，每个四维超立方体由8个正方体构成。

云云...

所以这题最终的解法就是O(b)从f[a][0]递推。

代码

int a, b;
ll f[100010], inv[200020];
ll ksm(ll base, int p){
    ll res = 1;
    while(p){
        if(p & 1){
            res *= base;
        }
        base *= base;
        res %= mod;
        base %= mod;
        p >>= 1;
    }
    return res;
}
void GetInv(){
    inv[1] = 1;
    for(int i = 2; i <= a * 2; ++i){
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    }
    return;
}
int main(){
    scanf("%d%d", &a, &b);
    if(a < b){
        printf("0
");
        return 0;
    }
    f[0] = ksm(2, a);
    GetInv();
    for(int i = 1; i <= a; ++i){
        f[i] = f[i - 1] * (a - i + 1) % mod * inv[i * 2] % mod;
    }
    for(int i = 0; i <= a; ++i){
    }
    printf("%lld
", f[b]);
	return 0;
}