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

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();
}
上一篇:大数据:Spark Core(二)Driver上的Task的生成、分配、调度


下一篇:[转帖][超级少儿不宜]一氧化氮(NO),为什么亚洲人是最硬