bzoj1008 / P3197 [HNOI2008]越狱

P3197 [HNOI2008]越狱

考虑所有状况：显然是$m^{n}$

考虑所有不合法状况：

显然相邻两个数不相等

那么后面$n-1$个数就有$(m-1)^{n-1}$种取法

第一个数前面没有相邻的，那么就有$m$种取法

∴不合法状况有$m*(m-1)^{n-1}$种

∴$ans=m^{n}-m*(m-1)^{n-1}$

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #define re register

 using namespace std;

 typedef long long ll;

 const int mod=1e5+;

 ll m,n;

 ll ksm(ll x,ll y){

     ll res=;

     for(;y;y>>=){

         if(y&)res=res*x%mod;

         x=x*x%mod;

     }return res;

 }

 int main(){

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

     printf("%lld",(ksm(m,n)-m%mod*ksm(m-,n-)%mod+mod)%mod);

     return ;

 }

巴特西

bzoj1008 / P3197 [HNOI2008]越狱

最新文章

热门文章