洛谷P3750 [六省联考2017]分手是祝愿(期望dp)

时间:2023-12-31 13:08:38

传送门

嗯……概率期望这东西太神了……

先考虑一下最佳方案,肯定是从大到小亮的就灭(这个仔细想一想应该就能发现)

那么直接一遍枚举就能$O(nlogn)$把这个东西给搞出来

然后考虑期望dp,设$f[i]$表示从$i$个正确选项中选择一个正确的变为$i-1$个的期望次数

那么$$f[i]=\frac{i}{n}+(1-\frac{i}{n})*(1+f[i+1]+f[i])$$

其中$\frac{i}{n}$表示一次就选了正确的选项,$(1-\frac{i}{n})$表示按错了,那么会增加一个正确选项,然后这个时候要按回去次数是$(1+f[i+1]+f[i])$,然后再加上按错的一次

那么移项可得$$f[i]=1+\frac{(n-i)*(f[i]+1)+1}{n}$$

然后只要从后往前递推就可以了

 //minamoto
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
inline int read(){
#define num ch-'0'
char ch;bool flag=;int res;
while(!isdigit(ch=getc()))
(ch=='-')&&(flag=true);
for(res=num;isdigit(ch=getc());res=res*+num);
(flag)&&(res=-res);
#undef num
return res;
}
const int N=,mod=;
int b[N];vector<int> g[N];
int f[N],inv[N],n,k;
void solve(){
int ans=,tp=;
for(int i=;i<=n;++i)
for(int j=i;j<=n;j+=i)
g[j].push_back(i);
for(int i=n;i;--i)
if(b[i]){
++tp;
for(int j=,s=g[i].size();j<s;++j) b[g[i][j]]^=;
}
if(tp<=k) ans=tp;
else{
f[n]=;
for(int i=n-;i;--i) f[i]=(1ll+1ll*(n-i)*(f[i+]+)*inv[i])%mod;
for(int i=tp;i>k;--i) (ans+=f[i])%=mod;
(ans+=k)%=mod;
}
for(int i=;i<=n;++i) ans=1ll*ans*i%mod;
printf("%d\n",ans);
}
int main(){
// freopen("testdata.in","r",stdin);
n=read(),k=read();
for(int i=;i<=n;++i) b[i]=read();
inv[]=;
for(int i=;i<=n;++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
solve();
return ;
}