bzoj4872 分手是祝愿

发表于 | 分类于

题目描述

B 君在玩一个游戏，这个游戏由 n 个灯和 n 个开关组成，给定这 n 个灯的初始状态，下标为从 1 到 n 的正整数。

每个灯有两个状态亮和灭，我们用 1 来表示这个灯是亮的，用 0 表示这个灯是灭的，游戏的目标是使所有灯都灭掉。

但是当操作第 i 个开关时，所有编号为 i 的约数（包括 1 和 i）的灯的状态都会被改变，即从亮变成灭，或者是从灭变成亮。

B 君发现这个游戏很难，于是想到了这样的一个策略，每次等概率随机操作一个开关，直到所有灯都灭掉。

这个策略需要的操作次数很多， B 君想到这样的一个优化。如果当前局面，可以通过操作小于等于 k 个开关使所有灯都灭掉，那么他将不再随机，直接选择操作次数最小的操作方法（这个策略显然小于等于 k 步）操作这些开关。

B 君想知道按照这个策略（也就是先随机操作，最后小于等于 k 步，使用操作次数最小的操作方法）的操作次数的期望。

这个期望可能很大，但是 B 君发现这个期望乘以 n 的阶乘一定是整数，所以他只需要知道这个整数对 100003 取模之后的结果。

输入输出格式

输入格式：
第一行两个整数 n, k。

接下来一行 n 个整数，每个整数是 0 或者 1，其中第 i 个整数表示第 i 个灯的初始情况。

输出格式：
输出一行，为操作次数的期望乘以 n 的阶乘对 100003 取模之后的结果。

输入输出样例

输入样例：
5 0
1 0 1 1 1
输出样例：
5120

说明

• 对于 0% 的测试点，和样例一模一样；

• 对于另外 30% 的测试点， n ≤ 10；

• 对于另外 20% 的测试点， n ≤ 100；

• 对于另外 30% 的测试点， n ≤ 1000；

• 对于 100% 的测试点， 1 ≤ n ≤ 100000; 0 ≤ k ≤ n；

• 对于以上每部分测试点，均有一半的数据满足 k = n。

分析

原来存的是差分的期望步数啊。。。

先枚举倍数求出最小需求操作开关次数
设f[i]表示从有i个正确选择变为有i-1个正确选择的期望操作次数
$f[i]=\frac{i}{n}+\frac{n-i}{n}*(1+f[i+1]+f[i])$
$f[i]=\frac{n}{i}+\frac{(n-i)f[i+1]}{i}$
显然f[n]=1 然后就可以递推求和了

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
const ll mod=100003;
int a[101010];
bool s[101010];
int n,K,num;
ll f[101010],ans;
ll power(ll x,ll k)
{
    ll sss=1;
    while (k)
    {
        if (k%2) sss=sss*x%mod;
        x=x*x%mod;
        k/=2;
    }
    return sss;
}
ll ny(int x)
{
    return power(x,mod-2);
}
int main()
{
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
    scanf("%d%d",&n,&K);
    for (int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    for (int i=n;i>=1;--i)
    {
        int x=a[i];
        for (int j=i+i;j<=n;j+=i)
            x^=s[j];
        s[i]=x;
        if (x) ++num;
    }
    if (num<=K)
    {
        ans=num;
        for (int i=1;i<=n;++i)
            ans=ans*i%mod;
        printf("%lld\n",ans);
        return 0;
    }
    f[n]=1;
    for (int i=n-1;i>K;--i)
        f[i]=(n*ny(i)%mod+(n-i)*f[i+1]%mod*ny(i)%mod)%mod;
    for (int i=K+1;i<=num;++i)
        ans=(ans+f[i])%mod;
    ans=(ans+K)%mod;
    for (int i=1;i<=n;++i)
        ans=ans*i%mod;
    printf("%lld\n",ans);
    return 0;
}
--------------------------