排名好的徐州网站建设,如何注册网站域名备案,网站开发天晟合益,php7.0 wordpress 设置洛谷P3197 越狱 题目大意#xff1a; 监狱有 n 个房间#xff0c;每个房间关押一个犯人#xff0c;有 m 种宗教#xff0c;每个犯人会信仰其中一种。如果相邻房间的犯人的宗教相同#xff0c;就可能发生越狱#xff0c;求有多少种状态可能发生越狱。 答案对100,003 取模。… 洛谷P3197 越狱 题目大意 监狱有 n 个房间每个房间关押一个犯人有 m 种宗教每个犯人会信仰其中一种。如果相邻房间的犯人的宗教相同就可能发生越狱求有多少种状态可能发生越狱。 答案对100,003 取模。 对于 100% 的数据保证1≤m≤10^81≤n≤10^12。 学啥用啥
要求有多少种状态可能发生越狱我们可以求所有的安排牢房的状态 也就是全集。 然后再算出所有的不会越狱的状态也就是集合A。
用全集减去集合A得到补集这就是答案。 全集如何求
由乘法原理可知每个牢房都可以安排m种宗教也就是有m种选择一共有n个牢房那么全集就是 接下来我们要求所有不会越狱的状况集合A。
也就是要使得每个相邻的房间宗教不同。
第一个房间的选择有m种第二个房间的选择只要满足不和前面的房间相同即可m-1种
第三个房间只要满足与第二个房间不同也就是m-1种。
这样下来每个房间都与自己前一个房间的宗教不同从而使得每个相邻的房间宗教不同。 答案就是 所以最终答案就是 mod 100003
用快速幂即可
千万记住先输入m再输入n我被这个卡了好久
然后别忘了特判 快速幂之和可能会小于0再加上100003即可
#define _CRT_SECURE_NO_WARNINGS
#includeiostream
#includecstdio
#includecmath
#includestring
#includecstring
#includestring
#includealgorithm
#includevector
#includecctype
#includemap
#includeset
#includequeue
#includenumeric
#includeiomanip
using namespace std;
const long long MOD 100003;
typedef long long ll;
ll qpow(ll m, ll n) {ll s 1;while (n) {if (n 1)s s * m % MOD;m m * m % MOD;n 1;}return s;
}
ll n, m,ans,cns,bns;int main() {cin m n;ans qpow(m, n);bns (m * qpow(m - 1, n - 1))%MOD;cns (ans - bns)%MOD;if (cns 0)cns MOD;cout cns;
}
