NOIP 数学训练

第1题 LightOJ - 1027 A Dangerous Maze (期望)

LightOJ - 1027 A Dangerous Maze
题意:小Q在迷宫中,他站在$n$个门前面,每个门只有两个可能,要么在$A_i$时间后,回到原地,要么在$A_i$时间后离开迷宫。每次他都会随机选择一个门,计算他离开的期望时间。
解:设当前期望为$E$
如果选择了正数时间,那么期望值为$\frac{A_i}{n}$
如果选择了负数时间,那么期望值为$\frac{E-A_i}{n}$,因为浪费了$-A_i$的时间
然后让所有负数和为$T_0$,负数个数为$n_0$,正数和为$T_1$,正数个数为$n_1$
$E=\frac{T_1}{n}+\frac{n_0E-T_0}{n}$,整理可得$E=\frac{T_1-T_0}{n_1}$,用 GCD 约分一下

知识点:期望的递归定义在处理无法直接用普通式子表达的时候非常好用,最后化简式子即可。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {
    int gcd(int a, int b) {
        return (b == 0) ? a : gcd(b, a % b);
    }
    void clean() {}
    int solve() {
        int n, K, T0, T1, N1, kase = 0; 
        cin >> K;
        clean();
        while (K--) {
            T0 = 0, T1 = 0, N1 = 0;
            ++kase, cin >> n;
            for (int x, i = 1; i <= n; i++) {
                cin >> x;
                if (x < 0) T0 += x; else T1 += x, ++N1;
            }
            int x = -T0 + T1, y = N1;
            if (y == 0) printf("Case %d: inf\n", kase); else {
                int g = gcd(x, y);
                printf("Case %d: %d/%d\n", kase, x / g, y / g);
            }
        }
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

第2题 LightOJ - 1030 Discovering Gold (期望DP)

LightOJ - 1030 Discovering Gold
题意:有一个直线的金矿,每个点有一定数量的金子;你从$0$开始,每次扔个骰子,扔出几点就走几步,然后把那个点的金子拿走;如果扔出的骰子超出了金矿,就重新扔,知道你站在最后一个点;问拿走金子的期望值是多少
解:设$dp(i)$为从$i$到$n$的期望值,则$dp(i)=\frac{1}{x}\sum dp(i + j) + a_i$,其中$x$是不超出金矿的掷骰子次数。初始化$dp(i)=a_i$
答案是$dp(1)$。注意本题正推有问题,无法保证$dp(n)$由$1$推来。
我们类比飞行棋那题,发现那题因为出现了航线所以不能倒推,否则能倒推。并且本题因为不能掷骰子的数大于$n$,所以不能像飞行棋那题一样全部概率为定值,在边缘的概率不一样。
知识点:
1、要看期望DP的状态是否从无效状态推向有效来确定枚举顺序
2、每一步概率和为1,否则有错

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

int kase = 0;

namespace flyinthesky {

    int n, a[105];
    db dp[105];

    void clean() {
        ms(dp, 0);
    }
    int solve() {
        cin >> n;
        clean();
        for (int i = 1; i <= n; i++) cin >> a[i], dp[i] = a[i];
        for (int i = n - 1; i >= 1; i--) {
            db tmp = 0.0;
            int tms = 0;
            for (int j = 1; j <= 6; j++) {
                if (i + j <= n) tmp += dp[i + j], ++tms;
            }
            dp[i] = tmp / (db)tms + a[i];
        }
        printf("Case %d: %.7f\n", ++kase, dp[1]);
        return 0; 
    }
}
int main() {
    int T; cin >> T;
    while (T--) flyinthesky::solve();
    return 0;
}

第3题 Loj 10230/Bzoj 3398 牡牛和牝牛 (组合数学)

Loj 10230
题意:见上。
解:
方法1:DP
设$dp(i)$表示$i$位置以牡牛结尾的方案数。
那么$dp(i)=\sum^{i-k-1}{j=1} dp(j)$,使$pre(i)=\sum^{i}{j=1} dp(j)$,那么原转移方程变为$O(n)$,最后输出$pre(n)$即可。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MO = 5000011;

    LL n, k, dp[100000 + 5], pre[100000 + 5];

    void clean() {
    }
    int solve() {
        cin >> n >> k;
        clean();
        pre[0] = dp[0] = 1;
        for (LL i = 1; i <= n; i++) {
            dp[i] = pre[max(i - k - 1, 0ll)];
            pre[i] = (pre[i - 1] + dp[i]) % MO;
            //cout << dp[i] << " " << pre[i] << endl;
        }
        cout << pre[n];
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

方法2:排列组合
考虑枚举当前方案的牡牛只数$i$,可以知道每个犊牛间一定有$k$个牝牛,所以每次将这固定的$(i-1) \cdot k$个牝牛删除,然后再剩下的牛中选$i$个犊牛,将删除的牝牛加回来显然满足条件。所以答案是$C^{i}_{(i-1) \cdot k}$,因为这个组合数范围大不方便二维求出,我们预处理阶乘和阶乘逆元用定义法求解组合数。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MO = 5000011;

    LL n, k, jc[100000 + 5], jc_inv[100000 + 5];

    LL ksm(LL a, LL b) {
        LL bs = a % MO, ans = 1ll;
        while (b) {
            if (b & 1) ans = (ans * bs) % MO;
            bs = (bs * bs) % MO;
            b >>= 1ll;
        }
        return ans;
    }
    LL c(LL n, LL m) {
        if (m > n) return 0;
        LL tmp = jc[n];
        tmp = (tmp * jc_inv[m]) % MO;
        tmp = (tmp * jc_inv[n - m]) % MO;
        return tmp;
    }

    void clean() {
    }
    int solve() {
        cin >> n >> k;
        clean();
        jc[0] = jc[1] = 1ll;
        jc_inv[0] = jc_inv[1] = 1ll;
        for (int i = 2; i <= n; i++) {
            jc[i] = (jc[i - 1] * i) % MO;
            jc_inv[i] = (jc_inv[i - 1] * ksm(i, MO - 2)) % MO;
        }
        int ans = 0ll;
        for (int i = 1; i <= n; i++) {
            int tmp = n - (i - 1ll) * k;
            if (tmp < 0) break ;
            ans = (ans + c(tmp, i)) % MO;
        }
        cout << ans + 1ll;
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

知识点:
1、计数问题可以 1 DP 2 组合数学
2、DP 方程如果出现了求前缀DP和,可以用前缀和优化
3、排列组合中将定下来的东西删除或者添加不影响答案的东西(插板法求有空的部分)可以帮助解题
4、预处理能带入$n$就用$n$,防止 TLE

第4题 Loj 10231 方程的解 (组合数学)

Loj 10231
题意:见上。
解:显然插板法求。用快速幂算出$g(x)$,然后答案为$C^{k}_{g(x)}$,注意要高精度。代码没写高精

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    LL k, x, c[1005][1005];

    LL ksm(LL a, LL b, LL c) {
        LL bs = a % c, ans = 1ll;
        while (b) {
            if (b & 1) ans = (ans * bs) % c;
            bs = (bs * bs) % c;
            b >>= 1;
        }
        return ans;
    }

    void clean() {
        ms(c, 0);
    }
    int solve() {
        clean();
        cin >> k >> x;
        for (LL i = 0; i <= 1001; ++i) c[i][i] = c[i][0] = 1;
        for (LL i = 2; i <= 1001; ++i) {
            for (LL j = 1; j < i; ++j) c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
        }
        /*for (LL i = 0; i <= 10; ++i) {
            for (LL j = 0; j <= i; ++j) printf("%I64d%c", c[i][j], (j == i) ? '\n' : ' ');
        }*/
        LL gg = ksm(x, x, 1000ll);
        //cout << gg << endl;
        cout << c[gg - 1][k - 1];
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

第5题 Loj 10232 车的放置 (组合数学)

Loj 10232
题意:见上。
解:
方法1:排列组合
我们先考虑不被切掉一块的方法,很显然是$C^{n}{k} \cdot A^{k}{m}$,其中长为$n$, 宽$m$。

然后我们考虑切一块的方法,我们将它分成两个矩形来处理,然后枚举一个矩形放几个车,设当前枚举到$i$, 则最终答案加上$C^{a}{i} \cdot A^{i}{b} \cdot C^{a+c-i}{k-i} \cdot A^{k - i}{d}$

方法2:DP

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    LL MO = 100000 + 3;

    LL a, b, c, d, k, C[2005][2005];

    void clean() {
        ms(C, 0);
    }
    int solve() {
        cin >> a >> b >> c >> d >> k;
        clean();
        LL sz = a + c;
        for (LL i = 0; i <= sz; ++i) C[i][i] = C[i][0] = 1;
        for (LL i = 2; i <= sz; ++i) 
        for (LL j = 1; j < i; ++j) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MO;

        /*for (LL i = 0; i <= sz; ++i) 
        for (LL j = 0; j <= i; ++j) printf("%I64d%c", C[i][j], j == i ? '\n' : ' ');*/

        LL ans = 0ll;
        for (LL i = 0; i <= k; ++i) {
            LL tmp = C[a][i];
            for (LL j = b; j >= b - i + 1; --j) tmp = (tmp * j) % MO;
            tmp = (tmp * C[a + c - i][k - i]) % MO;
            for (LL j = d; j >= d - (k - i) + 1; --j) tmp = (tmp * j) % MO;
            ans = (ans + tmp) % MO;
        }
        cout << ans;
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

第6题 LightOJ - 1038 Race to 1 Again (期望DP)

LightOJ - 1038 Race to 1 Again
题意:给定一个整数$n$, 每次操作可以对当前数进行除以它的某个因子。除以哪个因子是随机的,求把$n$变成$1$的期望步数。
解:设$dp(i)$为$i$除到$1$的期望步数。
则$dp(i)=\frac{dp(a_1)+dp(a_2)+…+dp(a_n)}{m}+1$,其中$a_n | i$,我们将右边的$dp(i)$拿过来以后式子变为$dp(i)=\frac{dp(a_1)+dp(a_2)+…+dp(a_{n-1})+m}{m-1}$
然后DP即可,先进行DP后$O(1)$询问。

知识点:
1、这题使用了记忆化打表的思想
2、期望DP式子右边有$dp(i)$就移到左边
3、期望DP不要忘了转移花费

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    int n, p[100005], sz; //p[index] = val, sz is index
    db dp[100005]; //dp[val] = expected number

    void clean() {
    }
    int solve() {
        clean();
        dp[1] = 0.0;
        for (int x = 2; x <= 100000; ++x) {// x is val
            sz = 0;
            for (int i = 1; i * i <= x; ++i) { // i is val, x / i is val
                if (x % i == 0) p[++sz] = i;
                if (i != (x / i) && x % (x / i) == 0) p[++sz] = x / i;
            }
            for (int i = 1; i <= sz; ++i) dp[x] += dp[p[i]]; // i is index
            dp[x] += sz, dp[x] /= (db)(sz - 1);
        }
        int T, kase = 0; scanf("%d", &T);
        while (T--) {
            cin >> n;
            printf("Case %d: %.8f\n", ++kase, dp[n]);
        }
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

第7题 Bzoj 3505 输三角形 (组合数学)

Bzoj 3505

第8题 LightOJ - 1079 Just another Robbery (概率背包DP)

题意:XX想抢银行,当危险率低于$P$的时候才能行动,现在给出每家银行的金钱$m_i$和危险率$p_i$,求最多能获得多少金钱。
解:设$dp(i,j)$为前$i$个银行抢$j$元钱的不被抓概率。
$dp(i,j)=min(dp(i-1,j-w_i) \cdot (1-p_i))$
转移即可
知识点:
1、设概率求期望
2、正难则反思想

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

int kase = 0;

namespace flyinthesky {

    const db INF = 1000000000.0, eps = 1e-9;
    const int MAXV = 10005;

    db maxP, p[105], dp[10010];
    int n, w[105];

    void clean() {
        for (int i = 0; i <= MAXV; ++i) dp[i] = -INF;
    }
    int solve() {
        scanf("%lf%d", &maxP, &n);
        for (int i = 1; i <= n; ++i) scanf("%d%lf", &w[i], &p[i]);
        clean();
        dp[0] = 1.0;
        for (int i = 1; i <= n; ++i) {
            for (int j = MAXV; j >= w[i]; --j) {
                dp[j] = max(dp[j], dp[j - w[i]] * (1 - p[i]));
            }
        }
        int ans = 0;
        for (int j = MAXV; j >= 0; --j) {
            db tmp = 1.0 - dp[j];
            if (maxP - tmp > -eps) {
                ans = j; break;
            }
        }
        printf("Case %d: %d\n", ++kase, ans);
        return 0;
    }
}
int main() {
    int T; scanf("%d", &T);
    while (T--) flyinthesky::solve();
    return 0;
}

第9题 LightOJ - 1265 Island of Survival (期望)

LightOJ - 1265 Island of Survival
题意:有$ t $只老虎,$ d $只鹿,还有一个人,每天都要有两个生物碰面,现在有以下规则:老虎不管碰到谁都吃掉,同类的话就同归于尽。问人存活下来的概率。
解:如果老虎有奇数只,那么老虎绝对可以把人吃掉,概率为0
如果老虎有偶数只,那么老虎可以两两吃掉,并且人遇到鹿不会死,所以人存活的概率和鹿没关系。
所以我们从$t+1$个生物中选1个出来当做幸存者,那么人存活概率为$\frac{1}{t+1}$

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define LL long long
#define db double
#define ms(i, j) memset(i, j, sizeof i)

using namespace std;

namespace flyinthesky {

    void clean() {
    }
    int solve() {
        clean();
        int kase = 0, T; scanf("%d", &T);
        while (T--) {
            int t, d; scanf("%d%d", &t, &d);
            if (t % 2 == 0) printf("Case %d: %.8f\n", ++kase, 1.0 / (t + 1.0));
            else printf("Case %d: 0\n", ++kase);
        }
        return 0;
    }
};
int main() {
    flyinthesky::solve();
    return 0;
}

第10题 LightOJ - 10228 Discovering Gold (Lucas 定理)

#10228. 「一本通 6.6 例 3」组合
题意:见上。
解:发现 $ m $ 很小,我们用组合数阶乘定义式两边求,即先乘$(n-m+1)$到$n$,再除$m!$。然后因为 $ p $ 不一定和所要求逆元的数互质,所以我们要用 Lucas 定理来求,因为 Lucas 保证了每次的组合数$n, m$小于 $p$,并且$p$为质数,所以不会有不互质的情况。
知识点: Lucas 定理可以用来求模数和被求逆元数不互质下的组合数公式。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    LL n1, m1, p;

    LL ksm(LL a, LL b) {
        LL bs = a % p, ans = 1ll;
        while (b) {
            if (b & 1) ans = (ans * bs) % p;
            bs = (bs * bs) % p;
            b >>= 1;
        }
        return ans;
    }
    LL C(LL n, LL m) {
        LL ans = 1ll, ni = 1ll;
        for (LL i = n - m + 1; i <= n; ++i) ans = (ans * i) % p;
        for (LL i = 2; i <= m; ++i) ni = (ni * ksm(i, p - 2)) % p;
        return (ans * ni) % p;
    }
    LL lucas(LL n, LL m) {
        if (m == 0) return 1;
        return (C(n % p, m % p) * lucas(n / p, m / p)) % p;
    }

    void clean() {
    }
    int solve() {
        clean();
        cin >> n1 >> m1 >> p;
        cout << lucas(n1, m1) << endl;
        return 0;
    }
}
int main() {
    int T; scanf("%d", &T);
    while (T--) flyinthesky::solve();
    return 0;
}

第11题 Poj 1845 (分治+分解质因数+约数和公式 / 逆元讨论)

Poj 1845
题意:求$A^B$因子和。
解:这里主要讲讲等比数列求和方法。
可以用逆元,但是模的质数太小可能有倍数关系不存在逆元,但是可以通过同余来化简特判没逆元的情况。
也可以在$log(c)$的时间内分治求解, 具体看算法竞赛进阶指南上的解析,注意分治边界特判

注意$B=0$

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MO = 9901;

    LL A, B, pri[50000000 + 5], cnt[50000000 + 5], tot;

    LL ksm(LL a, LL b) {
        LL bs = a % MO, ans = 1ll;
        while (b) {
            if (b & 1) ans = (bs * ans) % MO;
            bs = (bs * bs) % MO;
            b >>= 1;
        }
        return ans;
    }
    LL sum(LL n, LL q) {
        if (n == 0) return 0;
        if (n == 1) return q + 1;
        if (n == 2) return q + 1 + q * q;
        if (n % 2 == 1) {
            return (1ll + ksm(q, (n + 1) >> 1)) * sum((n - 1) >> 1, q) % MO;
        } else {
            LL qtmp = ksm(q, n >> 1);
            LL qtmp2 = ksm(q, (n >> 1) + 1);
            return (qtmp + ((qtmp2 + 1ll) * sum((n >> 1) - 1, q) % MO)) % MO;
        }
    }

    void clean() {
        tot = 0;
    }
    int solve() {
        cin >> A >> B;
        if (B == 0) return cout << 1 << endl, 0;
        clean();
        for (LL i = 2; i * i <= A; ++i) {
            if (A % i == 0) {
                pri[++tot] = i;
                while (A % i == 0) A /= i, ++cnt[tot];
            }
        }
        if (A != 1) ++cnt[++tot], pri[tot] = A;
        LL ans = 1ll;
        for (LL i = 1; i <= tot; ++i) {
            ans = (ans * sum(cnt[i] * B, pri[i])) % MO;
        }
        cout << ans;
        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

第12题 P1365 WJMZBMR打osu! / Easy

WJMZBMR打osu! / Easy

利用两个数组DP,期望值计算

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    int n;
    db f[300000 + 5], g[300000 + 5];
    char s[300000 + 5];

    void clean() {
    }
    int solve() {

        clean();
        cin >> n;
        scanf("%s", s + 1);
        for (int i = 1; i <= n; ++i) {
            if (s[i] == 'o') 
                f[i] = f[i - 1] + 2.0 * g[i - 1] + 1.0, g[i] = g[i - 1] + 1.0;
            else if (s[i] == 'x')
                f[i] = f[i - 1], g[i] = 0.0;
            else 
                f[i] = f[i - 1] + g[i - 1] + 0.5, g[i] = (g[i - 1] + 1) / 2.0;
        }

        printf("%.4f\n", f[n]);

        return 0;
    } 
}
int main() {
    flyinthesky::solve();
    return 0;
}

第13题 CF 1154 G. Minimum Possible LCM

CF 1154 G. Minimum Possible LCM

可以枚举因数$d$,然后$O(n\ln n)$去找,然后算第一个和第二个的$\text{lcm}$即可,具体可以容易证明。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 1000000 + 5;

    LL n, a[MAXN], vis[10000000 + 5], ans = 1e18;
    LL g1, g2;

    LL gcd(LL a, LL b) {return b != 0 ? gcd(b, a % b) : a;}
    LL lcm(LL a, LL b) {return a * b / gcd(a, b);}

    void clean() {
    }
    int solve() {

        clean();
        cin >> n;
        for (LL i = 1; i <= n; ++i) {
            scanf("%lld", &a[i]);
            if (vis[a[i]]) {
                if (ans > a[i]) ans = a[i], g1 = vis[a[i]], g2 = i;
            }
            vis[a[i]] = i;
        }

        for (LL d = 1; d <= 10000000; ++d) {
            if (d >= ans) break ;
            LL h1 = 0, h2 = 0;
            for (LL j = d; j <= 10000000; j += d) {
                if (vis[j]) {
                    if (!h1) h1 = j; else if (!h2) h2 = j; else break;
                }
            }
            if (h1 && h2) {
                if (lcm(h1, h2) < ans) ans = lcm(h1, h2), g1 = vis[h1], g2 = vis[h2];
            }
        }

        if (g1 > g2) swap(g1, g2);
        cout << g1 << " " << g2 << endl;

        return 0;
    } 
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------