夏晓光(loveJY)的博客

六省联考D2T3

首先果然代码不长不毒瘤,而且这个关灯博弈之前还看过,就是忘了

然后有一些也推不太出来吧.....总的来说并不难,没有做D2T3潜质

题意：有一个长度为 $n$ 的 $01$ 串，下标编号 $1$ 到 $n$。对位置 $p$ 操作一次可以使所有编号为 $p$ 的约数的位置 $0$ 变 $1$，$1$ 变 $0$。目标是使所有位置变成 $0$。B 君先随机操作若干次，等到当前局面可以在 $k$ 次操作以内达成目标时就使用最优策略，达成目标后结束操作。求期望操作次数。

看见期望和奇怪的限制肯定是dp,但是并让人不好下手

于是本题最重要的一个贪心思想出现了

任何一个按键带来的影响都不能通过其他按键的组合表示出来

也就是说,如果这个按键现在是暗的,你按了的他,就一定要再按一次,否则一定不会达到全局暗的局面

这个形式好像就来源于唯一分解定理?

有了这个就真的可以DP了,我们考虑按照需要按的键数来设计状态,$f[i]$表示当前有i个需要按的键变到只需要有i-1个键的期望步数

然后我们考虑转移,

$f[i]=\frac{i}{n}+\frac{n-i}{i}(f[i+1]+f[i]+1)$

这个式子相当于我们有i/n概率按中正确的,而又有n-i/n概率炸掉,然后再按回来

整理一下$f[i]=\frac{n+(n-i)*(f[i+1])}{i}$

就可以O(n)递推了

假设原局面要cnt步

我们有了f数组,随机按之后到k就相当于只需要$f[cnt]+f[cnt-1]+f[cnt-2]....f[k+1]+k$这么多期望步就行了

如果k>=cnt?输出cnt啊你在想什么

注意乘上阶乘

code:

#include<iostream>
#include<cstdio>
#include<cstring>
const int MAXN = 2e5 + 7;
const int P = 100003;
int n, k;
int a[MAXN], vis[MAXN];
int fac[MAXN], ifac[MAXN];
int f[MAXN];

inline int ksm(long long x, int y) {
	long long ans = 1;
	while(y) {
		if(y & 1)ans = ans * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}

inline void init() {
	fac[0] = ifac[0] = 1;
	ifac[1] = 1;
	for(int i = 1; i <= n; ++i)fac[i] = 1ll * fac[i - 1] * i % P;
	ifac[n] = ksm(fac[n], P - 2);
	for(int i = n - 1; i >= 2; --i)ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
	return ;
}

inline int ni(int x) {
	return 1ll * ifac[x] * fac[x - 1] % P;
}

int main() {
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		vis[i] = a[i];
	}
	init();
	//printf("%d %d\n", fac[n], ifac[2]);
	int cnt = 0;
	for(int i = n; i >= 1; --i) {
		if(vis[i]) {
			for(int j = 1; j * j <= i; ++j) {
				if(i % j == 0) {
					vis[j] ^= 1;
					if(j != i / j)vis[i / j] ^= 1;
                    //判断原局面步数
				}
			}
			cnt++;
		}
	}
	if(k >= cnt)return printf("%lld\n", 1ll * cnt * fac[n] % P), 0;
	for(int i = n; i >= 1; --i) {
		f[i] = (n + (1ll * n - i) * f[i + 1]) * ni(i) % P;
		//printf("%d\n", f[i]);
	}//dp部分
	long long ans = k;
	for(int i = cnt; i > k; --i) {
		(ans += f[i]) %= P;
	}//统计答案
	printf("%lld\n", ans * fac[n] % P);
	return 0;
}