Description
Zeit und Raum trennen dich und mich.
时空将你我分开. B 君在玩一个游戏, 这个游戏由 n 个灯和 n 个开关组成, 给定这 n 个灯的初始状态, 下标为从 1 到 n 的正整数. 每个灯有两个状态亮和灭, 我们用 1 来表示这个灯是亮的, 用 0 表示这个灯是灭的, 游戏的目标是使所有灯都灭掉. 但是当操作第 i 个开关时, 所有编号为 i 的约数 (包括 1 和 i) 的灯的状态都会被改变, 即从亮变成灭, 或者是从灭变成亮. B 君发现这个游戏很难, 于是想到了这样的一个策略, 每次等概率随机操作一个开关, 直到所有灯都灭掉. 这个策略需要的操作次数很多, B 君想到这样的一个优化. 如果当前局面, 可以通过操作小于等于 k 个开关使所有灯都灭掉, 那么他将不再随机, 直接选择操作次数最小的操作方法 (这个策略显然小于等于 k 步) 操作这些开关. B 君想知道按照这个策略 (也就是先随机操作, 最后小于等于 k 步, 使用操作次数最小的操作方法) 的操作次数的期望. 这个期望可能很大, 但是 B 君发现这个期望乘以 n 的阶乘一定是整数, 所以他只需要知道这个整数对 100003 取模之后的结果.
Input
第一行两个整数 n, k.
接下来一行 n 个整数, 每个整数是 0 或者 1, 其中第 i 个整数表示第 i 个灯的初始情况.
1 ≤ n ≤ 100000, 0 ≤ k ≤ n;
Output
输出一行, 为操作次数的期望乘以 n 的阶乘对 100003 取模之后的结果.
- Sample Input
- 4 0
- 0 0 1 1
- Sample Output
- 512
思路
假设没有随机
我们考虑当前的最优算法, 肯定是从后往前来看有哪些需要被更新的
那么这样就很容易算出最开始我们最少需要走几步
然后是 \(dp_{i}\) 表示从最少 i 步走到最少 i-1 步的期望步数
我们考虑因为当前有 i 步都是需要走的, 所以当前这一步转移到 i-1 的概率是 \(\frac{i}{n}\)
然后就是走到 i+1, 概率 \(1-\frac{i}{n}\), 期望步数可以从 \(dp_{i+1}\) 转移
总的转移是 \(dp_{i}=\frac{i}{n}+(1-\frac{i}{n})*(1+dp_{i}+dp_{i+1})\)
移项消元得到 \(dp_{i}=\frac{n+(n-i)*dp_{i+1}}{i}\)
然后就做完了, 前缀和累加就行了
- #include<bits/stdc++.h>
- using namespace std;
- const int Mod = 1e5 + 3;
- const int N = 1e5 + 10;
- int n, k, a[N], f[N], fac = 1;
- int add(int a, int b) {
- return (a += b)>= Mod ? a - Mod : a;
- }
- int sub(int a, int b) {
- return (a -= b) <0 ? a + Mod : a;
- }
- int mul(int a, int b) {
- return 1ll * a * b % Mod;
- }
- int fast_pow(int a, int b) {
- int res = 1;
- for (; b; b>>= 1, a = mul(a, a)) {
- if (b & 1) res = mul(res, a);
- }
- return res;
- }
- int main() {
- scanf("%d %d", &n, &k);
- for (int i = 1; i <= n; i++) {
- scanf("%d", &a[i]);
- fac = mul(fac, i);
- }
- int num = 0;
- for (int i = n; i>= 1; i--) {
- for (int j = i <<1; j <= n; j += i) {
- a[i] ^= a[j];
- }
- if (a[i]) ++num;
- }
- for (int i = 1; i <= k; i++) f[i] = 1;
- for (int i = n; i> k; i--) {
- f[i] = mul(add(n, mul(n - i, f[i + 1])), fast_pow(i, Mod - 2));
- }
- int ans = 0;
- for (int i = 1; i <= num; i++) {
- ans = add(ans, f[i]);
- }
- printf("%d", mul(ans, fac));
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2876567.html