传送门:P3197
监狱有连续编号为 (1…N) 的 (N) 个房间，每个房间关押一个犯人，有 (M) 种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。
输入两个整数(M,N)。
Output
可能越狱的状态数，模 (100003) 取余。
Sample Output
题目大意
就是有n个房间，m个宗教，求可能相邻宗教的排列种数。
思路
题目求可能越狱的状态数，我们可以反过来看，求不可能越狱的状态数，不可能越狱的状态就是没有相邻的房间有相同的宗教，因为有m个宗教，所以第一个房间有m中宗教可选，第二个房间因为不能和前一个房间的宗教选一样的，所以只有m-1中情况，第三个房间也是这样，所以可以推出不可能越狱的状态数为(m*(m-1)^{n-1})，因为有n个房间,m个宗教，每个房间都可以从m个宗教里面选一个，所以总的排列数为(m^n)，我们的答案也就很明显了，就是可能越狱的状态数=总的状态数-不可能越狱的状态数，所以答案(ans = m^n-m*(m-1)^{n-1})。
代码
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
36
37
38
39
40
41
42
43
|
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e5+5;
const int mod = 100003;
ll (ll a,ll b){
ll ret = 1;
while(b){
if(b&1) ret = ret * a % mod;
a = a * a % mod;
b >>= 1;
}
return ret;
}
int main(void){
ll m, n;
scanf("%lld %lld",&m,&n);
ll ans = quick_pow(m,n)-m*quick_pow(m-1,n-1);
printf("%lldn",(ans%mod + mod)%mod);
return 0;
}
|
近期评论