![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiAzNfRHLGZkRGZkRfJ3bs92YsYTMfVmepNHL90TUl9Gazg1cONzYuJlMMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnLwETO1EDNwIjM4EzNwEjMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
l i n k link link
分析:
這題挺有意思的 考慮起來有點麻煩
首先 n n n維空間的點數 為 2 n 2^n 2n 因為每往外延伸一條邊 就多出兩個點
然後考慮遞推 設 f i , j f_{i,j} fi,j 表示 i i i維空間内 含有 j j j維空間的個數
從身邊最熟悉的 3 3 3維空間開始推
f 3 , 0 = 8 f_{3,0}=8 f3,0=8 因為 2 3 = 8 2^3=8 23=8 前面已經得出了
f 3 , 1 = 12 f_{3,1}=12 f3,1=12 因為每個點可以延伸出 3 3 3條邊 每條邊連着 2 2 2個點 那就是 f 3 , 0 × 3 2 = 12 \frac{f_{3,0}\times3}{2}=12 2f3,0×3=12
f 3 , 2 = 6 f_{3,2}=6 f3,2=6 因為每條邊可以延伸出 2 2 2個面 每個面連着 4 4 4條邊 就是 f 3 , 1 × 2 4 = 6 \frac{f_{3,1}\times 2}{4}=6 4f3,1×2=6
f 3 , 3 = 1 f_{3,3}=1 f3,3=1 雖然不用解釋 但還是模拟下上面的過程
每個邊延伸出 1 1 1個立方體 每個立方體連着 6 6 6個面
那就是 f 3 , 2 × 1 6 = 1 \frac{f_{3,2}\times 1}{6}=1 6f3,2×1=1
找規律了 分母都是 j × 2 j\times 2 j×2 分子是 f i , j − 1 × ( i + 1 − j ) f_{i,j-1}\times (i+1-j) fi,j−1×(i+1−j)
那麼 f i , j = f i , j − 1 × ( i + 1 − j ) / ( j × 2 ) f_{i,j}=f_{i,j-1}\times(i+1-j)/(j\times 2) fi,j=fi,j−1×(i+1−j)/(j×2)
然後把 i i i套成 a a a 先求出 2 a 2^a 2a 也就是 f a , 0 f_{a,0} fa,0
f n , i = f n , i − 1 × ( n + 1 − j ) / ( j × 2 ) f_{n_,i}=f_{n,i-1}\times(n+1-j)/(j\times2) fn,i=fn,i−1×(n+1−j)/(j×2) 就可以省去 f f f的一維
由于要除 又要 m o d mod mod 1000000007 1000000007 1000000007是質數 就乘 j × 2 j\times2 j×2關于 m o d mod mod 1000000007 1000000007 1000000007的乘法逆元 費馬小定理即可
CODE:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+5,Mod=1000000007;
ll a,b,f[N];
ll ksm(ll a,ll k)
{
ll res=1;
while(k)
{
if(k&1) (res*=a)%=Mod;
k>>=1;
(a*=a)%=Mod;
}
return res;
}
int main(){
scanf("%lld%lld",&a,&b);
f[0]=ksm(2,a);
for(int i=1;i<=b;i++)
f[i]=(f[i-1]*(a+1-i))%Mod*ksm((i<<1),Mod-2)%Mod;
printf("%lld",f[b]);
return 0;
}