Bzoj 1008(找规律+快速幂/乘法原理+快速幂)

BZOJ 1008
方法1:
这种要求方案数而且范围大的,一般都是打表找规律题。通过暴力打表,发现$m=2$的时候答案就是$2^n-2$,所以按照这个继续找规律,发现$m=3$的时候答案是$3^n$减一些有倍数关系的数,然后可以得出答案是$m^n-m(m-1)^{n-1}$
方法2:
对于$1-n​$等类似的排列计数问题,以动态规划和组合数学2种大方向为基本解决方向。每个格子有$m$种选择,有$n$个格子,所以总方案数为$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
25
26
27
28
29
30
31
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MO = 100003;
LL m, n;
LL poww(LL a, LL b) {
LL ret = 1, s = a;
while (b) {
if (b & 1) ret = (ret * s) % MO;
s = (s * s) % MO;
b >>= 1;
}
return ret;
}
void clean() {}
void solve() {
clean();
LL a1 = poww(m, n), a2 = poww(m-1, n-1), a3 = (m * a2) % MO;
printf("%lld\n", (a1 - a3 + MO) % MO);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
while (scanf("%lld%lld", &m, &n)==2) solve();
return 0;
}

暴力:

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MO = 100003;
int n, m, h[1000], ans;
void dfs(int a) {
if (a == n + 1) {
// printf("\n");
// for (int i=1;i<=n;i++) printf("%d ", h[i]);
for (int i=1;i<=n;i++) if (h[i] == h[i - 1]) {ans++; return ;}
} else {
for (int i=1;i<=m;i++) {
h[a] = i;
dfs(a + 1);
h[a] = 0;
}
}
}
void clean() {
ans = 0, ms(h, 0);
}
void solve() {
clean();
dfs(1);
printf("%d\n", ans % MO);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("2.out", "w", stdout);
#endif
while(scanf("%d%d", &m, &n)==2) solve();
return 0;
}

------ 本文结束 ------