P3750 [六省联考2017]分手是祝愿 期望DP

题意：

戳这里

分析：

我们发现，高位的按钮会影响到低位的按钮，但低位的按钮不会影响到高位，也就是说，我们得到了一个贪心求得最小策略的方法，那就是从高位向低位，灯亮就按按钮

得到了策略之后我们要开始考虑怎么算的操作次数的期望，我们不难发现，操作次数的期望和局面没有直接关系了，因为我们可以求出每一种局面下的最优策略且操作顺序不影响局面的形成，所以操作次数为 (i) 的局面可以看成一种等价的类，这就提示我们按照操作次数为状态进行 DP，我们设 (f_i) 表示从 (i) 次操作的局面转移向 (i-1) 次操作的局面的期望次数

每次有两种转移：

1. 直接按对剩下的 (i) 次操作中的一个按钮，直接转移
2. 按错了按钮，回到了 (i+1) 次的局面，必须先回到 (i) 次，再转移向 (i-1)

易得转移式如下：

(f_i=frac{i}{n}+frac{n-i}{n} imes(f_{i+1}+f_i+1))

移项化简得到

(f_i=frac{n+(n-i) imes f_{i+1}}{i})

然后先处理出初始局面的最优操作次数，和 (k) 比较一下，大于的话 DP 求出到 (k) 的期望次数再 (+k) , 不然直接就是最优操作次数

代码：

#include<bits/stdc++.h>
#define pii pair<int,int>
#define mk(x,y) make_pair(x,y)
#define lc rt<<1
#define rc rt<<1|1
#define pb push_back
#define fir first
#define sec second
#define inl inline
#define reg register

using namespace std;

namespace zzc
{
	inline int read()
	{
		int x=0,f=1;char ch=getchar();
		while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
		while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
		return x*f;
	}
	
	const int maxn = 1e5+5;
	const int mod = 1e5+3;
	int n,k,ans,cnt;
	vector<int> p[maxn];
	int sta[maxn],f[maxn],inv[maxn];
	
	void work()
	{
		n=read();k=read();
		inv[0]=inv[1]=1;
		for(int i=1,j=1;i<=n;i++,j=i) 
		{
			sta[i]=read();
			if(i!=1) inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
			while(j<=n)
			{
				p[j].pb(i);
				j+=i;
			}
		}
		for(int i=n;i;i--) 
		{
			if(sta[i]) {cnt++;for(auto j:p[i]) sta[j]^=1;}
			f[i]=1ll*(n+1ll*(n-i)*f[i+1]%mod)%mod*inv[i]%mod;
		}
		if(cnt<=k) ans=cnt;
		else
		{
			for(int i=cnt;i>k;i--) ans=(ans+f[i])%mod;
			ans=(ans+k)%mod;
		}
		for(int i=1;i<=n;i++) ans=1ll*ans*i%mod;
		printf("%d
",ans);
	}

}

int main()
{
	zzc::work();
	return 0;
}