1008: [HNOI2008]越狱

题目： http://61.187.179.132/JudgeOnline/problem.php?id=1008

快速幂
总共有m^n种状态
不会越狱的状态是与前一个的信仰不一样
第一个人可以有m种信仰
后面每个人的信仰只要和前一个不一样就行 所以每个人可以有m-1种信仰
总共有m*(m-1)^(n-1)种
会越狱的状态数就等于状态总数减去不会越狱的状态数
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const long long x=100003;

long long n,m;

long long mi(long long m,long long n)
{
    m%=x;
    if (n==0) return 1;
    if (m==0) return 0;
    if (n==1) return m;
    long long k=mi(m,n/2);
    k%=x;
    if (n%2==0) return (k*k%x);
    else return (((k*k%x)*m)%x);
}

int main()
{
    cin>>m>>n;
    m%=x;
    long long k=(mi(m,n)%x-m*mi(m-1,n-1))%x;
    //cout<<mi(m,n)<<' '<<m*mi(m-1,n-1)<<endl;
    if (k>=0) cout<<k<<endl;
    else cout<<k+x<<endl;
    return 0;
}
posted on 2012-09-18 17:09 Kiro 阅读(101) 评论(0)  编辑 收藏 引用 所属分类: 衡八oj

只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理