「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)=\begin{cases}i & i\le k \\ \frac in f(i-1)+\frac {n-i}n f(i+1)+1 & i\gt k\end{cases}$$

拆分$f(i)$：

$$nf(i)=i\cdot f(i-1)+(n-i)f(i+1)+n$$ $$i\cdot f(i)+(n-i)f(i)=i\cdot f(i-1)+(n-i)f(i+1)+n$$ $$i(f(i)-f(i-1))=(n-i)(f(i+1)-f(i))+n$$

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

$$g(i)=\frac {n-i}i\cdot g(i+1)+\frac ni$$

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

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

---

代码

#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;
}