[HNOI2008]越狱

倒。。这么水的题目都有的。。
Link:61.187.179.132:8080/JudgeOnline/showproblem
正着想有点麻烦。。倒过来想。。
一共有m^n种情况,其中不能越狱的情况中,如果从左往右考虑的话,第一个是m种,其余都是m-1种
所以就是(m-1)^(n-1)*m。。用一个二分计算乘方就可以了。。
减一下就可以了囧。。
Code:

#include<iostream>
using namespace std;
typedef long long ll;
const int mod=100003;
ll m,n;
inline void mul(ll&a,int b){a*=b;a%=mod;}
int power(ll x,int base)
{
if(x==0) return 1;
ll tmp=power(x/2,base);
mul(tmp,tmp);
if(x&1) mul(tmp,base);
return tmp;
}
int main()
{
cin>>m>>n;
int all=power(n,m);
ll sub=power(n-1,m-1);
mul(sub,m);
int ans=all-sub;if(ans<0) ans+=mod;
cout<<ans<<endl;
}
本高亮代码使用codeHl生成,

4 thoughts on “[HNOI2008]越狱

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>