这两天遇到不少这种“人类智慧题”了，感觉都是很巧妙的

Description

link

现在有 \(n\) 盏灯，设每一次操作控制第 \(i\) 占灯，而改变状态的灯就是 \(i\) 的所有约数

现在给定初始的灯的状态序列，求剩余k次操作，就把灯全部关闭的步数期望\(+k\)和\(n!\) 的乘积

答案对 \(10003\) 取模

\(n \leq 10^5\)

Solution

思路分析

上来我们看到了“期望”，直接想到这题要 \(dp\)

然后定义状态是个难题（下面没有扯淡了）

\(f[i]\) 表示离全关掉还有 \(i\) 步走到离全关掉还有 \(i-1\) 步的期望操作次数。（这里是重点）

转移的时候考虑两种情况：

\(1^0\) 一次性摁对了，这种情况有\(\frac{i}{n}\)的概率

\(2^0\) 一次摁不对，需要转到\(i+1\)的状态

所以转移方程直接给出

\[f[i]=\frac{i}{n}+\frac{f[i+1] \times (n-i) }{n}
\]

整理得：

\[f[i]=\frac{n+(n-i) \times f[i+1]}{i}
\]

算法流程

最后给出本题流程：

1.\(O(n \sqrt n)\) 预处理因数的个数

2.从后往前扫一下，看一共需要几次完成游戏（特判如果\(cnt \leq k\)，就直接乘上阶乘走人就好）

3.跑一下上面的 \(dp\),\(O(n)\)的，也不用优化

逆元啥的不会先去学板子吧

4.最后记得成阶乘

Code

#include <bits/stdc++.h>

using namespace std;

#define int long long

namespace yspm {

inline int read() {

    int res = 0, f = 1;

    char k;

    while (!isdigit(k = getchar()))

        if (k == '-')

            f = -1;

    while (isdigit(k)) res = res * 10 + k - '0', k = getchar();

    return res * f;

}

const int N = 1e5 + 10;

vector<int> vec[N];

int n, k, f[N], mod = 100003, now[N], cnt, fac = 1, ans;

inline void prework() {

    for (int i = 1; i <= n; ++i) {

        for (int j = i; j <= n; j += i) vec[j].push_back(i);

    }

    for (int i = n; i >= 1; --i)

        if (now[i]) {

            ++cnt;

            int sz = vec[i].size();

            for (int j = 0; j < sz; ++j) now[vec[i][j]] = !now[vec[i][j]];

        }

    return;

}

inline int ksm(int x, int y) {

    int res = 1;

    for (; y; y >>= 1) {

        if (y & 1)

            (res *= x) %= mod;

        (x *= x) %= mod;

    }

    return res;

}

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

signed main() {

    n = read();

    k = read(); f[n]=1;

    for (int i = 1; i <= n; ++i) now[i] = read(), (fac *= i) %= mod;

    prework();

    if (cnt <= k)

        return cout << cnt * fac % mod << endl, 0;

    for (int i = n - 1; i > k; --i) f[i] = (n + (n - i) * f[i + 1] % mod) % mod * inv(i) % mod;

    for (int i = cnt; i > k; --i) (ans += f[i]) %= mod;

    cout << (ans+k) * fac % mod << endl;

    return 0;

}

}  // namespace yspm

signed main() { return yspm::main(); }

巴特西

LGOJ3747 六省联考2017 分手是祝愿

Description

Solution

思路分析

算法流程

Code

最新文章

热门文章