[bzoj 4872] [Shoi2017]分手是祝愿

n盏灯, 有的亮有的灭, n个开关, 编号均为1~n. 按一下开关i, 所有编号为i的约数的灯的状态被切换一次. 所有灯熄灭时游戏结束. 等概率随机按开关, 直到游戏可以在k步之内结束; 此时, 执行最优策略. 求游戏结束的期望步数, 输出它乘以n!模(10^5+3)的结果. (1≤n≤10^5, 0≤k≤n) 没能自己搞出来......TAT

学习了一下WrongAnswer神犇的题解.

先考虑k=n, 即直接执行最优策略的情况.

我是这样想的: 开关i可以切换i的状态, 且不会影响编号大于i的灯, 所以从右往左贪心地模拟一遍即可. 由于操作是顺序无关的, 这也说明, 模2意义下, 最优解是唯一的.

然而, 除非把约数预处理出来, 否则, 这样是的.

WA神犇是这样做的: 设i号灯的初始状态为, 开关i按了次, 那么

简单地做到了.

然后想想k=0......没什么思路......其实不难啊......

把需要按的开关的数目看作状态, 这就是一个马尔可夫过程. 尝试建立递推关系. 设为还有x个开关待按, 游戏结束的期望步数. - 当, 根据题意, . - 当, 有的概率转移到, 的概率转移到, 所以.

可以用高斯消元解这个方程, 但是数据范围不允许.

一个比较好的办法是, 考虑, 即, 使待按的开关减少1个的期望步数. - 当, . - 当, 的概率按下待按的开关, 的概率按错, 这样, 就期望需要步挽回错误, 再走步按下一个正确的开关. . - 当, .

的部分从后往前递推即可. .

这样为什么能够成功呢? 可以从哲学的角度解释一下......差分是一个降维/降阶的好办法. ovo

下面代码中的e即上面所述的d.

const int MOD = 1e5 + 3, N = 1e5;

typedef long long ll;

ll inv[N+1], e[N+1];
int a[N+1], x[N+1];

int main()
{
	int n, k, s = 0;
	scanf("%d%d", &n, &k);
	rep (i, 1, n+1) scanf("%d", a+i);
	per (i, n, 1) {
		x[i] = a[i];
		for (int j = i+i; j <= n; j += i)
			x[i] ^= x[j];
		s += x[i];
	}

	inv[1] = 1;
	rep (i, 2, n+1) inv[i] = MOD - MOD/i * inv[MOD%i] % MOD;
	
	e[n] = 1;
	per (i, n-1, k+1)
		e[i] = (n + (n-i)*e[i+1]) * inv[i] % MOD;
	rep (i, 1, k+1)
		e[i] = 1;
	
	ll ans = 0;
	rep (i, 1, s+1) (ans += e[i]) %= MOD;
	rep (i, 2, n+1) (ans *= i) %= MOD;
	
	printf("%lld\n", ans);

	return 0;
}