题解：P1999 高维正方体

· · 题解

参考资料

题意简述

求 a 维空间的超立方体有几个 b 维结构。

解题思路

将超立方体视为 [0,1]^a，每个 b 维结构等价于选取 b 个坐标自由变化，其余 a-b 个坐标分别固定为 0 或 1，因此答案为：

C_a^b2^{a-b}

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int mod=1e9+7;
ll Pow(ll a,ll b)
{
    a%=mod;
    ll res=1;
    while(b)
    {
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
ll C(ll a,ll b)
{
    if(a<b||b<0)return 0;
    ll p=1,q=1;
    for(ll i=a-b+1;i<=a;i++)p=p*i%mod;
    for(ll i=1;i<=b;i++)q=q*i%mod;
    return p*Pow(q,mod-2)%mod;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll a,b;
    cin>>a>>b;
    cout<<C(a,b)*Pow(2,a-b)%mod<<'\n';
    return 0;
}