【BZOJ4872】分手是祝愿（动态规划，数学期望）

题面

BZOJ

题解

对于一个状态，如何求解当前的最短步数？

从大到小枚举，每次把最大的没有关掉的灯关掉

暴力枚举因数关就好

假设我们知道了当前至少要关\(tot\)次

如果一个灯被动两次以上是没有任何意义的

所以，相当于，要动的灯只有\(tot\)个

其他的是没有任何意义的

所以，题面可以变为：

现在有\(tot\)个\(1\)，\(n-tot\)个\(0\)

每次随机选择一个数将其异或\(1\)

求最终变为\(0\)的期望

我们现在考虑一下

设\(f[x]\)为剩下\(x\)个\(1\)的期望

并且我们知道了所有的值，

那么，我们不难推出：

也就是

同时，我们有边界：

\(f[x]=x(x\leq K)\)

\(f[n]=f[n-1]+1\)

如果考虑把\(f[n]\)带入到\(f[n-1]\)的式子中

我们可以得到只有\(f[n-1],f[n-2]\)之间的关系式

如此递推下去就可以推出\(f[K+1]\)和\(f[K]\)的关系式

这样就是常数项了

回朔带回去就可以求解

时间复杂度\(O(nlogn)\)

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 120000

#define MOD 100003

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int fpow(int a,int b)

{

	int s=1;

	while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}

	return s;

}

int tot,n,K;

int a[MAX],ans[MAX];

int inv[MAX];

int DFS(int x,int ss)

{

	if(x<=K)return ans[x]=x;

	ss=(1ll*n*inv[x]%MOD+1ll*ss*(n-x)%MOD*inv[x]%MOD)%MOD;

	return ans[x]=(DFS(x-1,ss)+ss)%MOD;

}

int main()

{

	n=read();K=read();

	for(int i=1;i<=n;++i)a[i]=read();

	for(int i=n;i;--i)

		if(a[i])

		{

			for(int j=1;j*j<=i;++j)

				if(i%j==0)

				{

					a[j]^=1;

					if(j*j!=i)a[i/j]^=1;

				}

			++tot;

		}

	if(tot<=K)

	{

		for(int i=1;i<=n;++i)tot=1ll*tot*i%MOD;

		printf("%d\n",tot);

		return 0;

	}

	for(int i=1;i<=n;++i)inv[i]=fpow(i,MOD-2);

	DFS(n,1);

	for(int i=1;i<=n;++i)ans[tot]=1ll*ans[tot]*i%MOD;

	printf("%d\n",ans[tot]);

	return 0;

}