[六省联考2017] 分手是祝愿

Luogu P3750

bzoj 4872

思路

期望DP小水题

然而我一眼并不会,我好菜啊


首先考虑所有灯都采用最小的次数关,似乎可以贪心地关

因为一个灯按两次相当于不按,所以按一个灯的次数要么是$0$,要么是$1$

从大到小枚举所有灯,只要当前的灯是开着的,就将它关一下,就可以统计出来最优的操作次数$tot$

这样你就可以拿到80分的好成绩(感觉好坑啊,最多给20就行了)


考虑如何期望DP求从当前最优操作次数为$tot$到当前最优操作次数为$k$的期望操作次数

设$f_i$为从当前最优操作次数为$i$到当前最优操作次数为$i-1$的期望操作次数,则有

$$f_i=\frac{i}{n}+\frac{n-i}{n}\cdot (1+f_{i+1}+f_i)$$

化简得

$$f_i=\frac{n}{i}+\frac{n-i}{i}\cdot f_{i+1}$$

将答案胡乱统计一下即可


代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

typedef long long LL;

const int MAXN=100010, MOD=100003;
int N, K, sta[MAXN], tot;

std::vector<int>vec[MAXN];

int mul(const int &_, const int &__){return int((LL)_*__%MOD);}
int ksm(int _, int __){
    int ans=1;
    while(__){
        if(__&1) ans=mul(ans, _);
        _=mul(_, _);
        __>>=1;
    }
    return ans;
}
int inv(const int &_){return ksm(_, MOD-2);}

int dp(){
    int f[MAXN], ans=0; f[N]=1;
    for(int i=N; i>K; i--)
        f[i]=(mul(N, inv(i))+mul(mul(N-i, inv(i)), f[i+1]))%MOD;
    for(int i=tot; i>K; i--) ans=(ans+f[i])%MOD;
    return (ans+K)%MOD;
}

int main(){
    scanf("%d%d", &N, &K);
    for(int i=1; i<=N; i++) scanf("%d", &sta[i]);
    for(int i=1; i<=N; i++)
        for(int j=i; j<=N; j+=i)
            vec[j].push_back(i);
    for(int i=N; i; i--) if(sta[i]){
        for(int j=0; j<vec[i].size(); j++)
            sta[vec[i][j]]^=1;
        tot++;
    }
    int ans;
    if(tot>=K) ans=dp();
    else	   ans=tot;
    for(int i=1; i<=N; i++) ans=mul(ans, i);
    printf("%d\n", ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注