「Bzoj 1008」「HNOI2008」越狱 (找规律+快速幂/乘法原理+快速幂)

发表于 | 分类于 | | + s

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}$

正解：

#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;
}

暴力：

#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;
}
------ 本文结束 ------