Description：

有 $n$ 个灯 $n$ 个开关，给出灯的初始状态，操作每个灯会使得他的所有约数编号的灯状态改变，刚开始随机操作，当发现当前局面的最少操作次数 $\leqslant k$ 的时候按最少操作次数操作，求操作次数的期望。

$1\leqslant n\leqslant 10^5$

Solution：

先说一下这道题用到的思想：

减少冗余状态， $DP$ 的时候观察题目性质，会发现一些东西是等价的 $/$ 冗余的 $/$ 没用的，那么就可以在设计状态的时候把他们合并 $/$ 换一种状态定义 $/$ 扔掉。

对于当前某一个状态，考虑它的最少操作次数是什么，不难发现一定是从高往低把亮的按灭，因为低的不会影响高的，所以高的只能由他自己或者更高的改变，那么选它自己显然更优。

由于同时按一个两次相当于没按，那么如果当前状态按 $i$ 次能按完的话，那么按一次要么次数加一，要么次数减一，他们的概率分别是 $\frac in$ 和 $\frac {n-i}n$ 。

这个时候会发现一个神奇的结论，就是对于一个状态，他到底是哪个亮哪个暗是没有本质区别的，也就是说所有最少按 $i$ 次按完的状态都是等价的。

那么就可以先求出起始状态需要按几次，然后设 $f[i]$ 表示从 $i$ 按到 $i-1$ 的期望步数。

感觉好多期望题都是设一个变量变化一的期望步数，最后把答案累加就是答案了（ JZOJ 5814 ），转移为： $$ f[i]=\frac i n\times 1+\frac{n-i}n(1+f[i+1]+f[i]) $$ 移个项就是： $$ f[i]=\frac{n+(n-i)f[i+1]}i $$ 这样一直推到 $k+1$ 把 $f$ 累加再加 $k$ 就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n,k;

#define MAXN 100010

vector<int> d[MAXN];

int a[MAXN];

int f[MAXN];

#define MOD 100003

int power(int a,int b)

{

	int res = 1;

	while(b > 0)

	{

		if(b & 1)res = 1ll * res * a % MOD;

		a = 1ll * a * a % MOD;

		b = b >> 1;

	}

	return res;

}

int main()

{

	scanf("%d%d",&n,&k);

	for(int i = 1;i <= n;++i)

		for(int j = i;j <= n;j += i)

			d[j].push_back(i);

	for(int i = 1;i <= n;++i)

		scanf("%d",&a[i]);

	int tot = 0;

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

	{

		if(a[i])

		{

			for(vector<int>::iterator it = d[i].begin();it != d[i].end();++it)

			{

				a[*it] ^= 1;

			}

			++tot;

		}

	}

	if(tot <= k)

	{

		int ans = tot;

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

		cout << ans << endl;

		return 0;

	}

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

	{

		f[i] = 1ll * (n + 1ll * (n - i) * f[i + 1] % MOD) % MOD * power(i,MOD - 2) % MOD;

	}

	int ans = 0;

	for(int i = tot;i > k;--i)

	{

		ans = (ans + f[i]) % MOD;

	}

	ans = (ans + k) % MOD;

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

	cout << ans << endl;

	return 0;

}