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

题面

题解

对于一个状态，如何求解当前的最短步数？
从大到小枚举，每次把最大的没有关掉的灯关掉
暴力枚举因数关就好

假设我们知道了当前至少要关(tot)次
如果一个灯被动两次以上是没有任何意义的
所以，相当于，要动的灯只有(tot)个
其他的是没有任何意义的
所以，题面可以变为：
现在有(tot)个(1)，(n-tot)个(0)
每次随机选择一个数将其异或(1)
求最终变为(0)的期望

我们现在考虑一下
设(f[x])为剩下(x)个(1)的期望
并且我们知道了所有的值，
那么，我们不难推出：

[f[x]=frac{x}{n}(f[x-1]+1)+frac{n-x}{n}(f[x+1]+1) ]

也就是

[f[x]=frac{x}{n}f[x-1]+frac{n-x}{n}f[x+1]+1 ]

同时，我们有边界：
(f[x]=x(xleq 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
",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
",ans[tot]);
	return 0;
}