[BZOJ1008][HNOI2008]越狱（排列组合）

Description

---

监狱有连续编号为1…N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱

Input

---

输入两个整数M，N.1<=M<=10^8,1<=N<=10^12

Output

---

可能越狱的状态数，模100003取余

Sample Input

---

2 3

Sample Output

---

6

HINT

---

6种状态为(000)(001)(011)(100)(110)(111)

Solution

---

敲一道水题放飞一下自我0 0，写题解以示尊重 总的方案数-没有相同宗教相邻的方案数 mn−m∗(m−1)n−1

#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #define Mod 100003 using namespace std; typedef long long ll; ll Pow(ll x,ll n) { ll res=1; x%=Mod; while(n>0) { if(n&1) { res*=x; res%=Mod; } x=(x*x)%Mod; n>>=1; } return res; } int main() { ll m,n; scanf("%lld%lld",&m,&n); printf("%lld",(Pow(m,n)-(m*Pow(m-1,n-1)%Mod)+Mod)%Mod); return 0; }