简单网站建设优化,我的世界找建筑网站,网站中的幻灯片ie6显示 ie7如何兼容,北海做网站题目
监狱有连续编号为 11 到 n 的 n 个房间#xff0c;每个房间关押一个犯人。
有 m 种宗教#xff0c;每个犯人可能信仰其中一种。
不存在没有信仰的犯人。
如果相邻房间的犯人信仰的宗教相同#xff0c;就可能发生越狱。
求有多少种状态可能发生越狱。
输入格式
共…题目
监狱有连续编号为 11 到 n 的 n 个房间每个房间关押一个犯人。
有 m 种宗教每个犯人可能信仰其中一种。
不存在没有信仰的犯人。
如果相邻房间的犯人信仰的宗教相同就可能发生越狱。
求有多少种状态可能发生越狱。
输入格式
共一行包含两个整数 m和 n。
输出格式
可能越狱的状态数对 100003100003 取余。
数据范围
1≤m≤108 1≤n≤1012
输入样例
2 3输出样例
6样例解释
所有可能的 66 种状态为(000)(001)(011)(100)(110)(111)(000)(001)(011)(100)(110)(111)。
代码
#includeiostreamusing namespace std;typedef long long LL;const int mod 100003;int qmi(int a, LL b)
{LL res 1;while(b){if(b 1) res res * a % mod;b 1;a (LL) a * a % mod;}return res;
}int main()
{int m;LL n;cin m n;// mod防止出现负数情况 cout (qmi(m, n) - (LL)m * qmi(m - 1, n - 1) % mod mod) % mod endl;// 总分配方案数 - 不会发生越狱的方案数//不会发生越狱时第一个人随便分配第二个人信仰为m - 1, 第三个人信仰也为 m - 1 return 0;
}
