codeforces838D - Airplane Arrangements

太妙啦！

我们把座位摆成一个环，在添加另一个座位，表示坐了这个位置就会有人生气，那么我们现在要求的就是没人坐它的方案数Ans，但是这个并不好求，我们发现对于每个位置，它们的Ans都是一样的，而且Ans的和就是在这n+1个中选位置选方向的所有方案数中的空位置之和。

所以Ans*(n+1)=All*(n+1-m)，All=(2(n+1))^m

 #include <cstdio>

 #define mod 1000000007

 using namespace std;

 int n,m;

 int qp(int a,int b){

     int c=;

     for(;b;b>>=,a=1ll*a*a%mod)

         if(b&)c=1ll*c*a%mod;

     return c;

 }

 int main(){

     scanf("%d%d",&n,&m);

     printf("%lld\n",1ll*qp(*(n+),m)*(n+-m)%mod*qp(n+,mod-)%mod);

     return ;

 }

巴特西

codeforces838D - Airplane Arrangements

最新文章

热门文章