信息学奥赛一本通 1618：越狱

题目链接：http://ybt.ssoier.cn:8088/problem_show.php?pid=1618

思路：

总方案数为 m ∗ m ∗ … ∗ m = m n m*m*…*m=m^n m∗m∗…∗m=mn

不发生越狱的方案数为 m ∗ ( m − 1 ) ∗ . . . ∗ ( m − 1 ) = m ∗ ( m − 1 ) n − 1 m*(m-1)*...*(m-1) = m*(m-1)^{n-1} m∗(m−1)∗...∗(m−1)=m∗(m−1)n−1

故发生越狱的方案数为 m n − m ∗ ( m − 1 ) n − 1 m^n-m*(m-1)^{n-1} mn−m∗(m−1)n−1。

对答案取余 ( m n − m ∗ ( m − 1 ) n − 1 )   %   m o d (m^n-m*(m-1)^{n-1}) \ \% \ mod (mn−m∗(m−1)n−1) % mod，即 ( m n   %   m o d − m ∗ ( m − 1 ) n − 1   %   m o d )   %   m o d (m^n \ \% \ mod - m*(m-1)^{n-1} \ \% \ mod) \ \% \ mod (mn % mod−m∗(m−1)n−1 % mod) % mod，

但是 m n   %   m o d m^n \ \% \ mod mn % mod 减去 m ∗ ( m − 1 ) n − 1   %   m o d m*(m-1)^{n-1} \ \% \ mod m∗(m−1)n−1 % mod 可能是负数，

所以还需要把负余数转换成正余数，即 ( m n   %   m o d − m ∗ ( m − 1 ) n − 1   %   m o d + m o d )   %   m o d (m^n \ \% \ mod - m*(m-1)^{n-1} \ \% \ mod + mod) \ \% \ mod (mn % mod−m∗(m−1)n−1 % mod+mod) % mod。

#include <iostream>

using namespace std;

typedef long long ll;

const int mod = 100003;

int qmi(int a, ll b, int m)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = (ll)res * a % m;
        a = (ll)a * a % m;
        b >>= 1;
    }
    return res;
}

int main()
{
    int m;
    ll n;
    cin >> m >> n;
    
    cout << (qmi(m, n, mod) - (ll)m * qmi(m - 1, n - 1, mod) % mod + mod) % mod << endl;
    
    return 0;
}