NOIP训练营试题及解析-死亡迷宫

问题描述

    众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。

 现在有一个迷宫，这个迷宫是由若干个正 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 <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

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<b?a-b+mod:a-b;}

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<m||m<0)return 0;

    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("%d\n",Mul(ans,qpow(n,mod-2)));

    return 0;

}

题解：