板子

ll ksm(ll a, ll k, ll mod) { ll r = 1; a = a%mod; for (; k; k >>= 1, a = a*a%mod) if (k & 1) r = r*a%mod; return r; }

原理不在赘述，主要是用于记录

例题

1、 模板题

题意：求 a^b mod m 源代码：

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; ll a, b, m; ll ksm(ll a, ll k) { ll r = 1; a = a%m; for (; k; k >>= 1, a = a*a%m) if (k & 1) r = r*a%m; return r; } int main() { cin >> a >> b >> m; cout << ksm(a, b) << endl; return 0; }

2、越狱

题意： 监狱有连续编号为1到n的n个房间，每个房间关押一个犯人。有m种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人信仰的宗教相同，就可能发生越狱。求有多少种状态可能发生越狱。对100003取余。

思路： 总共有 m^n 种状态，其中任意两个相邻监狱的犯人都信仰不同的宗教，共有 m*(m-1)^(n-1) 种状态，相减就是答案

源代码：

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; ll n, m; ll m1 = 100003; ll ksm(ll a, ll k) { ll r = 1; a = a%m1; for (; k; k >>= 1, a = a*a%m1) if (k & 1) r = r*a%m1; return r; } int main() { cin >> m >> n; cout << (ksm(m, n)-ksm(m-1, n-1)%m1*m%m1+m1)%m1 << endl; return 0; }