[HNOI2008]越狱

Dark_Archon · 2018-11-01 20:21:33 · 个人记录

利用反向思想，处理出不能越狱的情况，再与总情况相减即为所求
顺便，已经第二次死在取模没处理好上了，注意啊啊啊啊啊啊啊啊啊

#include<iostream>
#include<cstdio>
using namespace std;

const long long mod=100003;
long long n,m;

long long expow(long long base,long long pow)
{
    long long t;
    if(pow==1) return base;
    t=expow(base,pow/2)%mod;
    if(pow%2==0)
    {
        return t*t%mod;
    }
    else
    {
        t=t*t%mod;
        t=t*base%mod;
        return t;
    }
}

int main()
{
    scanf("%lld%lld",&n,&m);
    long long res=(expow(n,m)%mod-(expow(n-1,m-1)*(n%mod))%mod)%mod;
    while(res<0) res+=mod;
    cout<<res<<endl;
    return 0;
}