web analytics

BZOJ1008 /乘法原理+快速幂 解题报告

1008: [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)

分析:

很显然,这是一道数学题。起初来想这道题可能会去想怎么去组合会越狱的方式。但是我们发现。会越狱的情况只要是两个宗教在一起就可能会出现火花。而不越狱呢只要不坐在一起就好;所以这里组合的方向就出来了。我们可以用全部组合减去不会越狱的组合。嗯是这样。第一个位置有m种选择。第二个位置就有m-1种选择。之后一直到n都只会有m-1种选择。所以:

Ans = m^n - m * (m-1)^(n-1)

就是这样。贴出代码:

Post a Comment

You must be logged in to post a comment.