首页 > 代码库 > BZOJ1008 HNOI2008 越狱 快速幂
BZOJ1008 HNOI2008 越狱 快速幂
题意：监狱有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱
题解：设f[i]=有M种宗教i个房间时不发生越狱的方案数，显然f[1]=M，f[i]=f[i-1]*(M-1)。最后答案就是N^M-f[N]
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;#define ll long longconst ll P=100003;ll N,M;ll QuickPow(ll a,ll b){ a%=P,b%=P-1; ll t=(b&1?a:1); while(b>>=1){ a=a*a%P; if(b&1) t=a*t%P; } return t;}int main(){ cin >> M >> N; cout << (QuickPow(M,N)-M*QuickPow(M-1,N-1)%P+P)%P << endl; return 0;}
BZOJ1008 HNOI2008 越狱 快速幂
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。