头部背景图片
Decaku 's Blog |
Decaku 's Blog |

bzoj 1008 越狱

描述:

有n个人排成一列,一共有m种势力,每个人可能属于一个势力,相邻的人势力相同则不合法,一共有多少种可能的不合法状态。


思路:

所有的状态是$m^{n}$,正面很难求不合法的状态,所以想到先求合法状态,第一个人有$m$种选择,剩下的人都只有$m-1$种选择,所以答案就是$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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=100003;
ll m,n;
ll quick_pow(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1) res=(res*a)%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int main()
{
while(~scanf("%lld %lld",&m,&n))
{
ll ans=(quick_pow(m,n)-(m*quick_pow(m-1,n-1))%mod+mod)%mod;
printf("%lld\n",ans);
}
}
avatar Decaku 很菜但也很想carry