BZOJ 2467 解题报告

对于一个合格的程序员来说，掌握一定的数学知识是非常必要的，所以这次就开个数学专题玩玩。

不多说啥，上题目，我们直接分析题目！

首先ORZ stonepage神犇，一眼就看出我把快速幂写成快速乘了……

话说%2007为啥不是2007年的题？还TMD是市选，MDZZ；

算了不管他，我们说我们的：

由于题目要求一个生成树，那么我们就要保证所有的点在一个联通块里面，so，怎么做呢？

首先观察这一个图，我们很容易能发现，其实我们只需要删去n+1条边，那么怎么删呢？

首先外围的五边形只能每个最少删去一条边这样一共才刚刚删掉n条边。

所以我们肯定要在中心n边形上删去一条边。由于中心n边形的每条边都是所有五边形中的一条边，所以呢就相当于有一个五边形要删掉2条边。

手动枚举删掉两条边的五边形，发现这个五边形一共有4种删边方法。

对于剩下的删除一条边五边形们，就一共有5的n-1次方种删除方法。

由于中心多边形是n条边，所以我们要的方案总数就是ans = 5^（n-1） ×４×ｎ种，然后％ｐ就可以啦；

什么，你不知道怎么算？这个就是个快速幂的基本套路……

接下来上代码啦，发福利啦：

 #include <iostream>
 #include <cstdio>
 #include <cmath>
 #include <algorithm>
 #include <cstring>
 #include <cstdlib>
 using namespace std;
 int get_num(){
     int num = ;
     bool flag = false;
     char c;
     while((c = getchar()) == ' ' || c == '\n' || c == '\r');
     if(c == ' ')flag = true;
     else num = c - '';
     while(isdigit(c = getchar()))
         num = num *  + c - '';
     return (flag ? - : )*num;
 }
 int quick_pow(int x,int y,int p){
     int ans = ;
     for(;y;x = (x*x) % p,y >>= )
     if(y & ){
         ans = (ans * x)%p;
     }
     return ans;
 }
 int n,m,T,p = ;
 int main(){
     T = get_num();
     while(T--){
         n = get_num();
         int ans;
         ans  =  * quick_pow(,n-,p) * (n%p);
         ans %= p;
         printf("%d\n",ans);
     }
     return ;
 }
 /*
     srO stonepage orz;
 */

如果有什么意见，请留言我的邮箱[e-mail]，谢谢。