M_sea

洛谷3750 [六省联考2017]分手是祝愿
LuoguLOJ分析感觉很神仙的题。首先可以观察出一个性质:所有按键都不能被其它某些按键的组合替代。于是可以从大到...
扫描右侧二维码阅读全文
09
2019/07

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

Luogu

LOJ

分析

感觉很神仙的题。

首先可以观察出一个性质:所有按键都不能被其它某些按键的组合替代。

于是可以从大到小扫一遍,如果当前这个亮着就按掉,然后即可求出至少要按的按钮数 $cnt$ 。

考虑 DP 。设 $f[i]$ 表示由 $i$ 个正确选择变为 $i-1$ 个正确选择的期望操作次数。

转移方程为 $\displaystyle f[i]=\frac{i}{n}+\frac{n-i}{n}\times(f[i]+f[i+1]+1)$ ,意思是有 $\displaystyle\frac{i}{n}$ 的概率按到正确的选择,$\displaystyle\frac{n-i}{n}$ 的概率按到错误的选择。

这个转移方程两边都有 $f[i]$ ,考虑暴力化简,那么真正的转移方程就是 $\displaystyle f[i]=\frac{n+(n-i)\times f[i+1]}{i}$ 。

答案就是 $\displaystyle n!\sum_{i=k+1}^{cnt}f[i]$ 。注意特判 $cnt\leq k$ 的情况,依据题意此时答案应为 $n!\times cnt$ 。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;
const int mod=100003;

inline int qpow(int a,int b) {
    int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod)
        if (b&1) c=1ll*c*a%mod;
    return c;
}

int n,k,cnt,ans;
int a[N],f[N];

int main() {
    n=read(),k=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=n;i;--i) {
        if (!a[i]) continue;
        ++cnt;
        for (re int j=1;j*j<=i;++j) {
            if (i%j) continue;
            a[j]^=1; if (j*j!=i) a[i/j]^=1;
        }
    }
    for (re int i=n;i;--i)
        f[i]=(n+1ll*(n-i)*f[i+1]%mod)*qpow(i,mod-2)%mod;
    if (cnt<=k) ans=cnt;
    else {
        ans=k;
        for (re int i=cnt;i>k;--i) ans=(ans+f[i])%mod;
    }
    for (re int i=1;i<=n;++i) ans=1ll*ans*i%mod;
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 07 月 09 日 07 : 37 PM

发表评论