分手是住院「期望dp」 | Hexo

归档于 2019-10-01 21:09

这个题如果各位大神做的话肯定是”当时秒切”

像我这种据若就算了吧

题解

首先考虑没有随机的情况

从大到小枚举看是最优的,

感性理解,你大的一定要选,你如果小的选了之后你大的可能让当前小的翻转,你当前选的可能是无意义的,

(说人话就是你选大的可能会对小的造成影响,你选小的一定不会对大的造成影响)

设f[i]表示当你还剩i个开关要按时期望步数

那么题目中说最后k步选最优策略就没用了,f[i]一定会选择最优即一定按需要按的必须选的灯f[i]=1

那么考虑随机,

贡献分两部分,1.按你需要按的$\frac{i}{n}$2.按不需按的是$\frac{n-i}{n}*(f[i+1]+f[i]+1)$

解释一下,你选到不该选的,你要用$1$步到$f[i+1]$状态,然后你要用$f[i+1]$步翻转回来,,回到当前状态之后你还要花$f[i]$步达到当前选到正确灯状态(这个式子让我们想起了tree这个题,很像不是吗)

关于求必选集合,用$vector$维护约数就行了

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 1010101
#define mod 100003
ll f[A],a[A],inv[A];
ll cnt=0,n,k;
vector <ll> vec[A];
int main(){
    scanf("%lld%lld",&n,&k);
    f[n]=1;inv[1]=1;
    for(ll i=2;i<=n;i++) 
        inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    for(ll i=1,v;i<=n;i++)
        scanf("%lld",&a[i]);
    for(ll i=1;i<=n;i++)
        for(ll j=i;j<=n;j+=i)
            vec[j].push_back(i);
    for(ll i=n;i>=1;i--){
        if(!a[i]) continue ;
        for(ll j=0;j<vec[i].size();j++)
            a[vec[i][j]]^=1;
        cnt++;
    }
    for(ll i=n-1;i>k;i--)
        f[i]=(n+(n-i)*f[i+1]%mod)*inv[i]%mod;
    for(ll i=k;i>=1;i--)
        f[i]=1;
    ll ans=0;
    for(ll i=1;i<=cnt;i++)
        (ans+=f[i])%=mod;
    for(ll i=1;i<=n;i++)
        ans=ans*i%mod;
    printf("%lld\n",ans);
}

View Code