BZOJ4872 [Shoi2017]分手是祝愿

题面在这里

​

考虑最优策略是什么

从大到小，遇到亮的灯就按一下，感觉一下应该是最优的

那么问题就变成了有\(t\)个按钮需要按奇数次

\(f_i\)表示还有\(i\)个按钮需要按奇数次，则有： \[ f_i=\frac i n f_{i-1}+\frac {n-i} n f_{i+1} +1 \] 然而这并不太好搞，再转化一下：

\(g_i\)表示\(i\)个按钮到\(i-1\)个按钮需要的期望步数 \[ g_i=\frac i n + \frac {n-i} n (1+g_i+g_{i+1}) \\ g_i=\frac {(n-i)g_{i+1}+n} i \] \(g_n=1\)，答案就是\(k+\sum_{i=k+1}^t g_i\)

​

示例程序：

#include<cstdio>
#include<cmath>
typedef long long ll;

const int maxn=100005,MOD=100003;
int n,m,K,d[maxn];
ll f[maxn];
ll power(int a,int b){
	ll res=1,w=a;
	while (b){
		if (b&1) (res*=w)%=MOD;
		(w*=w)%=MOD;
		b>>=1;
	}
	return res;
}
int main(){
	scanf("%d%d",&n,&K);
	for (int i=1;i<=n;i++) scanf("%d",&d[i]);
	for (int i=n;i>=1;i--)
	 if (d[i]){
	 	int tj=sqrt(i);d[i]=0;m++;
	 	for (int j=1;j<=tj;j++)
	 	 if (i%j==0){
	 	 	d[j]^=1;
	 	 	if (j*j!=i) d[i/j]^=1;
		 }
	 }
	if (m<=K){
		ll ans=m;
		for (int i=1;i<=n;i++) (ans*=i)%=MOD;
		printf("%lld",ans);
		return 0;
	}
	ll ans=K;
	f[n]=1;
	for (int i=n-1;i>K;i--)
	 f[i]=((n-i)*f[i+1]+n)%MOD*power(i,MOD-2)%MOD;
	for (int i=m;i>K;i--) (ans+=f[i])%=MOD;
	for (int i=1;i<=n;i++) (ans*=i)%=MOD;
	printf("%lld",ans);
	return 0;
}