隐藏
「SHOI2017」分手是祝愿 - 期望动规+差分 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「SHOI2017」分手是祝愿 - 期望动规+差分

题目大意

    B 君在玩一个游戏,这个游戏由$n$个灯和$n$个开关组成,给定这$n$个灯的初始状态,下标为从$1$到$n$的正整数。每个灯有两个状态亮和灭,我们用$1$来表示这个灯是亮的,用$0$表示这个灯是灭的,游戏的目标是使所有灯都灭掉。但是当操作第$i$个开关时,所有编号为$i$的约数(包括$1$和$i$)的灯的状态都会被改变,即从亮变成灭,或者是从灭变成亮。
    B 君发现这个游戏很难,于是想到了这样的一个策略,每次等概率随机操作一个开关,直到所有灯都灭掉。这个策略需要的操作次数很多, B 君想到这样的一个优化。如果当前局面,可以通过操作小于等于$k$个开关使所有灯都灭掉,那么他将不再随机,直接选择操作次数最小的操作方法(这个策略显然小于等于$k$步)操作这些开关。
    B 君想知道按照这个策略(也就是先随机操作,最后小于等于$k$步,使用操作次数最小的操作方法)的操作次数的期望。
    这个期望可能很大,但是 B 君发现这个期望乘以$n$的阶乘一定是整数,所以他只需要知道这个整数对$100003$取模之后的结果。


题目分析

首先对于$n=k$,不难想到一种最优策略:
从右向左扫描,每遇到一个开着的灯就按按钮。
因为每一个灯只能被比他大的灯关掉,因此这样操作一定是最优的。
然后你就可以写出$50$分程序,实际上拿到了$80$分的优秀分数。

接下来,考虑这个最优策略,实际上是策略
无论怎么随机关灯开灯,最后都要还原后按照上述策略操作才能全部关掉。
因此,我们便能转化一下问题,转化为有$k$个位置的灯是不正确的,$n-k$个位置的灯是正确的,将不正确的灯全部变成正确的灯的期望步数。
这个$k$在使用最优策略时即可算出。

设$f(i)$表示还有$i$步可以结束(也就是有$i$个不正确的位置)的期望步数:

拆分$f(i)$:

令$g(i)=f(i)-f(i-1)$:

然后就可以递推了,答案即为$f(k)$。

不需要考虑差分式在$i=k+1$时不成立,因为转移是递推式而不是通项。


代码

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
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

inline LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}

const int maxn=100005,mod=100003;

int a[maxn];
LL n,k,inv[maxn],g[maxn],sum=0,fac=1;

int main() {
n=Get_Int();
k=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
for(int i=n; i>=1; i--) {
for(int j=2*i; j<=n; j+=i)a[i]^=a[j];
sum+=a[i];
fac=fac*i%mod;
}
inv[1]=1;
for(int i=2; i<=n; i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for(int i=1; i<=k; i++)g[i]=1;
g[n]=1;
for(int i=n-1; i>k; i--)g[i]=((n-i)*g[i+1]%mod+n)*inv[i]%mod;
LL ans=0;
for(int i=1; i<=sum; i++)ans+=g[i];
printf("%lld\n",ans*fac%mod);
return 0;
}
姥爷们赏瓶冰阔落吧~