问题描述     众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。  现在有一个迷宫，这个迷宫是由若干个正 n=(4,6) 边形组成的 k层迷宫。如果 k = 1 ，那么该迷宫就由单独一个正 nn边形组成；如果 k>1，则在 k-1 层的基础上，沿着所有最外层的边增加一个正 n边形，新增加的正 n边形若有重叠，则保留其中一个即可。具体可以参考下图：‍‍ 描述及代码解析 ▋  现在为了打破迷宫的结界，你需要在迷宫的某些边上开一扇门。你总共要开 rr 扇门，每条边最多打开一扇门。但是如果两种开门的方案通过旋转相同，那么视为同一种方案。以及由于是死亡迷宫，所以死了也是可以的，所以你并不需要保证你开门的方案能够让你走出去。求总共的方案数。 【输入格式】   一行三个正整数 n,k,r 。 【输出格式】   一行一个整数代表答案对 10^9+7 取模之后的结果。 【样例输入】4 2 2 【样例输出】32 【数据规模与约定】   对于20%的数据， k = 1。   对于另外20%的数据， r = 1 。   对于另外20%的数据， k = 3。   对于50%的数据， n = 4。 ‍‍  对于100%的数据，  ‍ 代码： 1 #include #include #include #include #include using namespace std; int n,k,r; const int N=100010,M=100000,mod=1e9+7; inline int Plus(int a,int b){return a+b>=mod?a+b-mod:a+b;} inline int Del(int a,int b){return a< p=""> inline int Mul(int a,int b){return a*1ll*b%mod;} inline int qpow(int a,int b){int s=1;while(b){if(b&1)s=Mul(s,a);a=Mul(a,a);b>>=1;}return s;} int fac[N],inv[N]; inline void get_pre(){     fac[0]=1;for(int i=1;i<=M;++i)fac[i]=Mul(fac[i-1],i);     inv[M]=qpow(fac[M],mod-2);     for(int i=M-1;i>=0;--i)inv[i]=Mul(inv[i+1],i+1); }inline int C(int n,int m){     if(n<0)return 0;<="" p="">     return Mul(Mul(fac[n],inv[m]),inv[n-m]); } int main(){     scanf("%d%d%d",&n,&k,&r);     get_pre();     int ans=0;     if(n==4){         int p=4*k*k;         ans=Plus(ans,C(p,r));         if(!(r&1)){             ans=Plus(ans,C(p>>1,r>>1));             if(!((r>>1)&1))ans=Plus(ans,Mul(2,C(p>>2,r>>2)));         }     }else{         int p=3*(3*k-1)*k;         ans=Plus(ans,C(p,r));//循环节为1         if(r%2==0)ans=Plus(ans,C(p>>1,r>>1));         if(r%3==0)ans=Plus(ans,Mul(2,C(p/3,r/3)));         if(r%6==0)ans=Plus(ans,Mul(2,C(p/6,r/6)));     }     printf("%dn",Mul(ans,qpow(n,mod-2)));     return 0; } 题解：  

--end--

声明：本文章由网友投稿作为教育分享用途，如有侵权原作者可通过邮件及时和我们联系删除：freemanzk@qq.com