信奥赛C++提高组csp-s之快速幂（案例实践1）

信奥赛C++提高组csp-s之快速幂（案例实践1）

题目描述

监狱有n nn个房间，每个房间关押一个犯人，有m mm种宗教，每个犯人会信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。

答案对100 , 003 100,003100,003取模。

输入格式

输入只有一行两个整数，分别代表宗教数m mm和房间数n nn。

输出格式

输出一行一个整数代表答案。

输入输出样例 #1

输入 1

2 3

输出 1

6

说明/提示

样例输入输出 1 解释

数据规模与约定

对于100 % 100\%100%的数据，保证1 ≤ m ≤ 10 8 1 \le m \le 10^81≤m≤108，1 ≤ n ≤ 10 12 1 \le n \le 10^{12}1≤n≤1012。

思路分析

我们采用总方案数减去不越狱的方案数：
总方案数为m n m^nmn，不越狱的方案数为m × ( m − 1 ) n − 1 m \times (m-1)^{n-1}m×(m−1)n−1（第一个房间有 m 种选择，之后每个房间都不能与前一个相同，故有 m-1 种选择）。
答案即为m n − m × ( m − 1 ) n − 1 m^n - m \times (m-1)^{n-1}mn−m×(m−1)n−1，对 100003 取模，注意处理负数。

由于 n 可达10 12 10^{12}1012，必须用快速幂计算幂次取模。
m和m-1在计算前先对模数取模，避免溢出。

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintMOD=100003;// 快速幂：求 a^b % modllqpow(ll a,ll b,ll mod){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}returnres;}intmain(){ll m,n;cin>>m>>n;// 总方案数 = m^n % MODll total=qpow(m,n,MOD);// 不越狱方案数 = m * (m-1)^(n-1) % MODll noCrime=m%MOD*qpow(m-1,n-1,MOD)%MOD;// 越狱方案数 = total - noCrime，取正模ll ans=(total-noCrime+MOD)%MOD;cout<<ans<<endl;return0;}

功能分析

1. 快速幂取模：qpow函数采用二进制分解指数的方法，时间复杂度O ( log ⁡ n ) O(\log n)O(logn)，能安全处理 n高达10 12 10^{12}1012的情况。
2. 防止溢出：计算前对底数取模，乘法后立即取模。
3. 负数处理：(total - noCrime + MOD) % MOD确保结果为非负。
4. 简洁变量：使用m, n对应宗教数和房间数，符合题目要求。

更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》：
https://blog.csdn.net/weixin_66461496/category_13113932.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.html

3、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html

4、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}