P1291 [SHOI2002]百事世界杯之旅

题目链接

假设当前已经有(k)个名字，设(a = frac{k}{n})，就是拿到一个已经有过名字的概率。

设在经过(t)次拿到新的名字，那么概率就是(a ^ {t - 1}(1 - a))。

那么期望次数就是(E(1 - a) = (1 - a) * 1 + (1 - a) * a * 2 + (1 - a) * a ^2*3... = (1 - a) * (1 + 2a + 3a^2...) = E(1) - E(a))。

我们还可以知道(E(a) = a + 2a^2 + 3a^3+... = E(1) - 1 - a - a^2 - a^3...)。

然后移个项就可以得到(E(1 - a) = 1 + a + a ^2 + a ^ 3 + ... = frac{1 - a^t}{1 - a})。

因为(0 < a < 1)，所以(a ^ t)接近于0，所以(E(1 - a) = frac{1}{1 - a} = frac{n}{n - k})。

所以我们最后的答案就是(displaystyle sum _{k = 0}^{n - 1} frac{n}{n - k})。

#include <bits/stdc++.h>

#define int long long

using namespace std;

inline long long read() {
    long long s = 0, f = 1; char ch;
    while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
    for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
    return s * f;
}

const int N = 40;
int n, tag;
long long tmpm, tmpz;

long long gcd(long long x, long long y) {
    return y == 0 ? x : gcd(y, x % y);
}

long long LCM(long long x, long long y) {
    return x * y / gcd(x, y);
}

signed main() {
    n = read();
    long long lcm = -1;
    if(n == 0) { printf("0
");return 0; }
    for(int k = 0;k < n; k++) {
        if(lcm == -1) lcm = n - k, tmpm = n - k, tmpz = n;
        else {
            lcm = LCM(lcm, n - k);
            tmpz = tmpz * (lcm / tmpm) + n * (lcm / (n - k));
            tmpm = lcm;
            long long g = gcd(tmpz, tmpm);
            tmpz /= g; tmpm /= g;
        }
    }
    if(tmpm == 1) printf("%lld
", tmpz);
    else {
        long long a = tmpz / tmpm, b = tmpz % tmpm, len = 0, len2 = 0;
        long long tmp = a, tmp2 = tmpm;
        do len ++; while(tmp /= 10);
        do len2 ++; while(tmp2 /= 10);
        for(int i = 1;i <= len; i++) cout << " ";
        printf("%lld
", b);
        printf("%lld", a);
        for(int i = 1;i <= len2; i++) cout << "-";
        printf("
");
        for(int i = 1;i <= len; i++) cout << " ";
        printf("%lld
", tmpm);
    }

    return 0;
}

P3802 小魔女帕琪

题目链接

设(N = displaystyle sum _{i = 1}^{7}a_i)。

首先我们假设一连串取出前七个不同的，那么它的概率就是：(P = frac{a_1}{N}*frac{a_2}{N - 1}*frac{a_3}{N - 2}*frac{a_4}{N - 3}*frac{a_5}{N - 4}*frac{a_6}{N - 5}*frac{a_7}{N - 6})。

然后我们发现取元素的顺序不同也是不同的方案，所以前七个释放大招的期望就是(E = 7！* P * 1)。

然后我们看第八个元素，我们知道([2, 8])也是可以释放大招的，于是我们又可以写出概率（第一个元素已经确定）：(P' = frac{a_1}{N}*frac{a_2}{N - 1}*frac{a_3}{N - 2}*frac{a_4}{N - 3}*frac{a_5}{N - 4}*frac{a_6}{N - 5}*frac{a_7}{N - 6} * frac{a_1 - 1}{N - 7})。

第八个元素其实是1到7都可以放的，而且我们又可以知道(displaystyle sum_{i = 1}^{7} frac{a_i - 1}{N - 7} = 1)。

所以前八个释放大招的期望就是(E' = 2 * 7！* displaystyle sum_{i = 1}^{7} P'* 1 = 2 * 7! * P * 1)。

以此类推，前n个释放大招的期望就是(E = 7! * (N - 6) * P)。

#include <bits/stdc++.h>

using namespace std;

inline long long read() {
    long long s = 0, f = 1; char ch;
    while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
    for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
    return s * f;
}

int a[8];
long double fac, sum, ans;

int main() {

    fac = 1; ans = 1;
    for(int i = 1;i <= 7; i++) {
        a[i] = read(); sum += a[i]; fac *= i;
    }
    if(sum < 7) { printf("0.000
"); return 0; }
    for(int i = 1;i <= 7; i++) {
        ans *= 1.0 * a[i] / (sum - i + 1);
    }
    printf("%.3Lf", fac * ans * (sum - 6));

    return 0;
}

P3750 [六省联考2017]分手是祝愿

题目链接

首先确定最小的操作次数(cnt)。我们从后往前扫，遇到亮着的就把他灭掉，这样可以求出最少操作次数。因为每一个灯可以将按得次数变为按或没有按，我们假设(p)位置的灯是亮着的，(p)后面的灯是关的，那么(p)这个灯只能通过按下自己使自己灭掉。这样找的话我们找到的是必须按下的灯，也就是其他灯不管是按了偶数次，相当于没按。

如果(cnt <= k)，那么答案就是(cnt * n!)。

如果(cnt > k)，我们需要求出让操作次数小于等于(k)的期望步数。

(f[i])表示让操作次数从(i)次变到(i - 1)次的期望步数，那我们可以列出DP转移方程：(f[i] = frac{i}{n} + frac{n - i}{n} * (f[i] * f[i + 1] + 1))。我们有(n)个灯，按到必须按的灯的概率（也就是可以让操作次数减小的灯的概率）是(frac{i}{n})，那么按到多余的灯的概率就是(frac{n - i}{i})，按到多余的灯就得把多的那一个操作次数按回来，就是乘上(f[i + 1])，因为要变到(i - 1)，所以还要乘上(f[i])，然后再加上1的错误操作。化简一下就可以变成(f[i] = frac{n + (n - i)f[i + 1]}{i})。

所以答案就是((f[cnt] + f[cnt - 1] + ... + f[k + 1] + k) * n!)。

#include <bits/stdc++.h>
    
using namespace std;
    
inline long long read() {
    long long s = 0, f = 1; char ch;
    while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
    for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
    return s * f;
}
    
const int N = 1e5 + 5, mod = 1e5 + 3;
int n, k, cnt, ans;
int a[N], f[N];

int ksm(int x, int y, int mod) {
    int res = 1;
    while(y) {
        if(y & 1) res = 1ll * res * x % mod;
        x = 1ll * x * x % mod; y >>= 1;
    }
    return res;
}

int inv(int x) {
    return ksm(x, mod - 2, mod);
}

int main() {
    
    n = read(); k = read();
    for(int i = 1;i <= n; i++) a[i] = read();
    for(int i = n;i >= 1; i--) {
        if(a[i]) {
            cnt ++;
            for(int j = 1;j * j <= i; j++) {
                if(!(i % j)) {
                    a[j] ^= 1;
                    if(j * j != i) a[i / j] ^= 1;
                }
            }
        }
    }
    for(int i = n;i >= 1; i--) f[i] = 1ll * (n + 1ll * (n - i) * f[i + 1] % mod) % mod * inv(i) % mod;
    if(cnt <= k) ans = cnt;
    else {
        for(int i = cnt;i >= k + 1; i--) ans = (ans + f[i]) % mod;
        ans = (ans + k) % mod;
    }
    for(int i = 1;i <= n; i++) ans = 1ll * ans * i % mod;
    printf("%d", ans);

    return 0;
}