思路
计算总状态数和不越狱的状态数之差。
总状态数为$M*N$，不越狱的状态数为$M∗(M−1)^{N−1}$。
用到快速幂。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
using namespace std;
typedef long long ll;
ll (ll a, ll b, ll n){
ll ret = 1;
while(b){
if(b & 1) ret = ret a % n;
a = a a % n;
b >>= 1;
}
return ret;
}
int main(){
ll m, n;
ll mod = 100003;
cin >> m >> n;
ll tmp = pow(m, n, mod)%mod - m*pow(m-1, n-1, mod)%mod;
cout << (tmp+mod)%mod << endl;
return 0;
}
|
一开始没过，因为没有 $(tmp + mod) mod mod$ 这段，而是直接输出tmp了，这样会溢出。
近期评论