[bzoj] 1008: [HNOI2008]越狱

发表于   |   分类于   |  

题意

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

传送门

分析

所有的可能宗教信仰方案为:$M^N$
相邻两个房间的人的宗教信仰不同的方案为:$M\cdot (M-1)^{N-1}$

$$ Ans=(M^N-M\cdot (M-1)^{N-1}) mod 100003$$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <cstdio>
 
#define  ansmod  100003LL
 
typedef long long ll ;
 
ll n , m , ans ;

ll pow(ll x , ll p) {
truell ret = 1 ;
truefor (x %= ansmod ; p ; x *= x , x %= ansmod , p >>= 1)
true    if (p & 1) ret *= x , ret %= ansmod ;
truereturn ret ;
}

int main() {
//  #define READ
    #ifdef  READ
        freopen(".in" ,"r",stdin ) ;
        freopen(".out","w",stdout) ;
    #endif
    scanf("%lld%lld", &m , &n) ;
    m %= ansmod ;
    ans = (pow(m,n-1)-pow(m-1,n-1))%ansmod ;
    ans *= m , ans %= ansmod ;
    while (ans < 0) ans += ansmod ;
    printf("%lld\n", ans) ;
    #ifdef  READ
        fclose(stdin) ; fclose(stdout) ;
    #else
        getchar() ; getchar() ;
    #endif
    return 0 ;
}

热评文章