高维正方体(找规律+二项式定理+逆元)

描述

传送门:洛谷-1999

0维空间的元素是点,这个毋庸置疑。

2个0维空间的元素可以围成一个1维空间的元素,线段。

4个1维空间的元素可以围成一个2维空间的元素,正方形。

6个2维空间的元素可以围成一个3维空间的元素,正方体。

8个3维空间的元素可以围成一个4维空间的元素,超正方体。

……

一个正方形中,有4个(顶)点,4条线段(边),1个正方形。

一个正方体中,有8个(顶)点,12条线段(棱),6个正方形(面),1个正方体。

……

我们的问题是:给出a与b,请求出:在a维空间的元素中,包含着多少个b维空间的元素。答案可能很大,只需要输出它除以1000000007的余数。

Input

两个整数a,b,以空格隔开。

Output

一个整数,即答案。

Examples

  • intput

    1
    3 1
  • output

    1
    12

思路

  • 仔细观察
    4 4 1
    8 12 6 1
    可以看出他们的共同点就是一个是$(x+2)^2$的展开式系数,一个是$(x+2)^3$的展开式系数,这时候我们就大胆的猜测$n$维立方体里包含的比他低维度的立方体个数就是$(x+2)^n$的展开式的系数,a维空间的元素中包含个b维空间的元素的个数就是$(x+2)^a$的展开式中$x^b$的系数。(事实证明是对的)
  • 根据二项式定理,我们就得到了公式
  • 由于$C_a^b2$和$2^{a-b}$都太大了,但是由于要取模,我们就可以分别用逆元和快速幂求得值。
  • 数据用$long   long$来存,否则会 爆精度。
  • 逆元和快速幂详见另一篇博客:数论笔记本

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef long long ll;
const double Pi = acos(-1);
const double e = 2.718281828459;
const int mod =1e9+7;

ll fac(ll x) //阶乘
{
ll ans=1;
for(int i=1;i<=x;i++)
ans=(ans*i)%mod;
return ans;
}

ll x,y;
ll exgcd(ll a,ll b) //扩展欧几里德求逆元
{
if(b==0)
{
x=1;y=0;
return a;
}
ll r=exgcd(b,a%b);
ll c=x;
x=y;
y=c-a/b*y;
return r;
}

ll qpow(ll a,ll b) //快速幂
{
ll ans=1;
a%=mod;
while(b>0)
{
if(b&1)
ans=(ans*a)%mod;
b/=2;
a=(a*a)%mod;
}
return ans;
}

int main()
{
int a,b;ll ans;
while(cin>>a>>b)
{
if(a<b) ans=0; //特判
else
{
exgcd((fac(b)*fac(a-b))%mod,mod);
x= x<=0? x+=mod:x; //保证x>0
ans=(((fac(a)*x)%mod)*qpow(2,a-b))%mod;
}
cout<<ans<<endl;
}
return 0;
}
-------------本文结束 感谢您的阅读-------------

本文标题:高维正方体(找规律+二项式定理+逆元)

文章作者:Armin

发布时间:2018年03月18日 - 22:03

最后更新:2018年07月30日 - 02:07

原始链接:http://x-armin.com/高维正方体/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

小礼物走一波