bzoj 4872: [Shoi2017]分手是祝愿 [期望DP]

时间：2023-02-06 05:37:37

4872: [Shoi2017]分手是祝愿

题意：n个灯开关游戏，按i后i的约数都改变状态。随机选择一个灯，如果当前最优策略\(\le k\)直接用最优策略。问期望步数\(\cdot n! \mod 1003\)

50% n=k 送分...从大到小选就行了...实际上送了80分...

这个期望DP没想到不应该啊

\(f[i]\)表示还有i步可以结束的期望步数

\[f[i] = \frac{i}{n} f[i-1] + \frac{n-i}{n}f[i+1] +1 \\
f[i+1] = ...
\]

但是k=0就gg了

考虑差分f，或者说\(g[i]\)表示i到i-1步的期望步数

\[g[i] = \frac{i}{n} + \frac{n-i}{n}(g[i+1] + g[i] + 1),\ g[n] = 1,\ g[i \le k]=1
\]

答案就是\(g[最优策略步数]\)啰

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N = 1e5+5, P = 100003, mo = P;

inline int read() {

    char c=getchar(); int x=0,f=1;

    while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}

    while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}

    return x*f;

}

int n, k, a[N];

int mark[N];

ll inv[N], g[N], fac = 1;

void solve() {

	int t = 0;

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

		int p = a[i];

		for(int j=i+i; j<=n; j+=i) if(mark[j]) p ^= 1;

		if(p) mark[i] = 1, t++;

	}

	if(t <= k) {printf("%lld", t * fac %mo); return;}

	inv[1] = 1;

	for(int i=2; i<=n; i++) inv[i] = (P - P/i) * inv[P%i] %P;

	for(int i=1; i<=k; i++) g[i] = 1;

	g[n] = 1;

	for(int i=n-1; i>k; i--) g[i] = ((n-i) * g[i+1] %mo + n) * inv[i] %mo;

	ll ans = 0;

	for(int i=1; i<=t; i++) ans += g[i];

	printf("%lld", ans * fac %mo);

}

int main() {

	freopen("in", "r", stdin);

	n=read(); k=read();

	for(int i=1; i<=n; i++) a[i] = read(), fac = fac * i %mo;

	solve();

}

相关文章