BZOJ2134: 单选错位【期望DP】

2134: 单选错位

【题目描述】

传送门

【题解】

我们考虑第i位和第i\%n+1位,第i位可以选择的范围是[1,a[i]],第a[i\%n+1]位能选择的范围是[1,a[i\%n+1]]
如果a[i]<a[i\%n+1]:如果i%n+1的答案大于a[i],那么不会造成贡献,如果小于等于a[i]才会造成贡献,所以期望取决于a[i\%n+1].
如果a[i]>a[i\%n+1]:同理,反过来。
如果a[i]==a[i\%n+1]:取决于任意一个。
所以最后答案就是\sum 1/max(a[i],a[i\%n+1])

代码如下

#include<cstdio>
using namespace std;
int n,A,B,C,a[10000005];double Ans=0;
int main(){
    scanf("%d%d%d%d%d",&n,&A,&B,&C,a+1); 
    for(register int i=2;i<=n;i++) a[i]=((long long)a[i-1]*A+B)%100000001; 
    for(register int i=1;i<=n;i++) a[i]=a[i]%C+1;
    for(register int i=1;i<=n;i++) Ans+=1.0/(a[i]<a[i%n+1]?a[i%n+1]:a[i]);
    printf("%.3lf\n",Ans);
    return 0;
}

发表评论

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部