Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom2年前

10/26
20:45
组合数/lucas

[bzoj 1008] HNOI2008 越狱

00:00/00:00

1-1510161I123   df60d1d243b6732156a9928a46df25db

♦♦♦♦♦♦   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)

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

总共可能的安排罪犯数为m^n,不会发生越狱的所有可能为m*(m-1)^(n-1)(每一个房间不能和前一个房间相同),所以最后的答案就是(m^n-m*(m-1)^(n-1)) mod 100003

c++:

pascal:

bdee50ca1dd85fbd9df84a08014c1f50

 

[bzoj 1008] HNOI2008 越狱