本文主要是介绍BZOJ 1008 [HNOI2008]越狱 (组合数 简单公式),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
[HNOI2008]越狱
Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 5714 Solved: 2439
[ Submit][ Status][ Discuss]
Description
监狱有连续编号为1...N的N个房间,每个房间关押一个犯人,有M种宗教,每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同,就可能发生越狱,求有多少种状态可能发生越狱
Input
输入两个整数M,N.1<=M<=10^8,1<=N<=10^12
Output
可能越狱的状态数,模100003取余
Sample Input
Sample Output
HINT
6种状态为(000)(001)(011)(100)(110)(111)
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1008
题目分析:首先题意不明确,应该是每个犯人都会信仰其中的一种,然后问题就简单了,拿总的可能减去相邻房间宗教不同的状态即可,第一个房间有m种选择,后面的n-1个房间的罪犯因为要与前一个不同都只有m-1种选择,问题解决
#include <cstdio>
#define ll long long
int const MOD = 100003;ll qpow(ll x, ll n)
{ll ans = 1;while(n){if(n & 1)ans = (ans * x) % MOD;x = (x * x) % MOD;n >>= 1;}return ans;
}int main()
{ll m, n;scanf("%lld %lld", &m, &n);printf("%lld\n", (MOD + qpow(m, n) % MOD - m * qpow(m - 1, n - 1) % MOD) % MOD);
}
这篇关于BZOJ 1008 [HNOI2008]越狱 (组合数 简单公式)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!