当前位置：首页 > news >正文

打卡信奥刷题（2524）用C++实现信奥 P1999 高维正方体

news 2026/5/12 19:47:23

P1999 高维正方体

题目描述

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

2 22个0 00维空间的元素可以围成一个1 11维空间的元素，线段。
4 44个1 11维空间的元素可以围成一个2 22维空间的元素，正方形。
6 66个2 22维空间的元素可以围成一个3 33维空间的元素，正方体。
8 88个3 33维空间的元素可以围成一个4 44维空间的元素，超正方体。

……

一个正方形中，有4 44个（顶）点，4 44条线段（边），1 11个正方形。
一个正方体中，有8 88个（顶）点，12 1212条线段（棱），6 66个正方形（面），1 11个正方体。

……

我们的问题是：给出a aa与b bb，请求出：在a aa维空间的元素中，包含着多少个b bb维空间的元素。答案可能很大，只需要输出它除以1 0 9 + 7 10^9+7109+7的余数。

输入格式

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

输出格式

一个整数，即答案。

输入输出样例 #1

输入 #1

3 1

输出 #1

说明/提示

样例解释

3 33维空间的元素是正方体，1 11维空间的元素是线段。所求即是一个正方体中棱的数量，为12 1212。

数据范围及约定

对于5 % 5\%5%的数据，a , b ≤ 1 a,b \le 1a,b≤1；
对于10 % 10\%10%的数据，a , b ≤ 2 a,b \le 2a,b≤2；
对于20 % 20\%20%的数据，a , b ≤ 3 a,b \le 3a,b≤3；
对于35 % 35\%35%的数据，a , b ≤ 4 a,b \le 4a,b≤4；
对于70 % 70\%70%的数据，a , b ≤ 1000 a,b \le 1000a,b≤1000；
对于100 % 100\%100%的数据，0 ≤ a , b ≤ 100000 0\le a,b \le 1000000≤a,b≤100000。

此外，对于15 % 15\%15%的数据，b = 0 b=0b=0，对于各10 % 10\%10%的数据，b = 1 b=1b=1或b = 2 b=2b=2。

提示

不保证a ≥ b a \ge ba≥b。

C++实现

#include<bits/stdc++.h>usingnamespacestd;#definep1000000007intf[100010],n,m;intqpow(intx,inty){intans=1;while(y>0){if(y&1)ans=(1LL*ans*x)%p;x=(1LL*x*x)%p;y>>=1;}returnans;}intmain(){scanf("%d%d",&n,&m);f[0]=qpow(2,n);for(inti=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]);return0;}