P3750 [六省联考2017]分手是祝愿[概率期望dp]

题目描述

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$ 取模之后的结果。

输入输出格式

输入格式:

第一行两个整数 $n$,$k$。

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

输出格式:

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

输入输出样例

输入样例#1:

1
2
4 0
0 0 1 1

输出样例#1:

1
512

输入样例#2:

1
2
5 0
1 0 1 1 1

输出样例#2:

1
5120

说明

• 对于 0% 的测试点,和样例一模一样;
• 对于另外 30% 的测试点, $n ≤ 10$;
• 对于另外 20% 的测试点, $n ≤ 100$;
• 对于另外 30% 的测试点, $n ≤ 1000$;
• 对于 100% 的测试点, $1 ≤ n ≤ 100000$ ; $0 ≤ k ≤ n$;
• 对于以上每部分测试点,均有一半的数据满足 $k = n$。

题解

最开始看错题了。操作第 $i$ 个开关时,所有编号为 $i$ 的 约数 状态改变。

很显然,对于某一个开关,按 $2$ 次=没按,所以只有按 $1$ 次和按 $2$ 次的区别。

所以最优解就是,从后往前扫,如果灯 $i$ 没有关,就改变 $i$ 和 $i$ 的约数的状态。

所以 $k=n$ 的 $50$ 分可以拿到了。

然后就是我没有想到的转移的方法。

如果最小步数 $\le k​$ 直接输出

设 $f_i$ 表示从第$i$步变成第 $i-1$ 步的期望

(有$ \frac {n-i}{n} $ 的概率走到第 $i+1$ 步,所以需要 $f_{i+1}$ 步回到第 $i$ 然后到第$i-1$步)

$$
f_i=\frac{i}{n}+\frac{n-i}{n}*(1+f_{i+1}+f_{i})
$$

$$
\frac {i}{n} * f_{i}=\frac{i}{n}+\frac {n-i}{n} × (1+f_{i+1})
$$

化一下就是

$$
f_i=\frac {(n-i)*(1+f_{i+1})}{i}
$$

答案就是 从第(最优步数)走到第 $k$ 步的期望加起来再加 $k$
(式子炸了的什么的直接开个markdown的预览,然后把那些东西丢进去)

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int qmax(int &x,int y) {if (x<y) x=y;}
int qmin(int &x,int y) {if (x>y) x=y;}
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
if(s==EOF)exit(0);if(s=='-')base=-1,s=getchar();
while(isdigit(s)){k=k*10+(s^'0');s=getchar();}
return k*base;
}
void write(int x)
{
if(x<0){putchar('-');write(-x);}
else{if(x/10)write(x/10);putchar(x%10+'0');}
}
const int maxn=1e5+10;
const int mod=100003;
int n,k,a[maxn],b[maxn];
ll s,ans;
ll f[maxn],inv[maxn];
vector<int> g[maxn];
int main()
{
n=read();k=read();
for (int i=1;i<=n;i++) a[i]=read(),s+=a[i],b[i]=a[i];
for (int i=1;i<=n;i++)
{
for (int j=i;j<=n;j+=i)
{
g[j].push\_back(i);
}
}//约数找出来
for (int i=n;i>=1;i--)
{
if (b[i])
{
for (int j=g[i].size()-1;j>=0;j--)
{
b[g[i][j]]^=1;
}
ans++;
}
}//最优解
if (ans<=k)
{//记得乘阶乘
for (int i=2;i<=n;i++) ans=ans*i%mod;
printf("%d\n",ans);
return 0;
}
s=ans;
ans=0;
inv[1]=1;
for (int i=2;i<=n;i++)
{
inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
}//预处理逆元
f[n]=1;
for (int i=n-1;i>=1;i--)
{
f[i]=(1+(long long)(n-i)*(1+f[i+1])*inv[i])%mod;
}
for (int i=s;i>k;i--) ans+=f[i],ans=ans>=mod?ans-mod:ans;
ans+=k;ans%=mod;
//求解
for (int i=2;i<=n;i++) ans=ans*i%mod;
printf("%d\n",ans);
return 0;
}